题解 CF2042C

· · 题解

题意：

给一个 0-1 串分段，每段内元素的分数从左到右递增，问使得位置为 1 的总分数至少比位置为 0 的总分数多 k 的最小段数。

思路：

算是一道有些反直觉的题目，一眼让人容易想到直接给序列本身分段，陷入错误循环。实际上得到正解只需要注意到一个结论：在某个位置 i 后断点，对总分数的贡献是一定的。而这个贡献等于 i 后的 1 个数减去 0 个数。

证明也不难，在 i 后断点，所有 i 之后的元素分数全部增加 1，对于前面答案的统计没有任何影响，断点之间也不会有任何影响。

只需从后往前枚举断点并且算出所有 n-1 个断点对答案的贡献，然后从大到小排序，贪心的取断点即可。

举个例子，考虑样例中 [0,0,1,1,1,0] 的字符串，设 i 后断点的贡献为 a_i，则有 a=[1,2,1,0,-1]。我们贪心的取断点，最多可以使得 1 个数和 0 个数之差达到 4。满足 k=3 的条件只需取两个 a，将序列分成三段。

程序如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int T,n,k,a[N];
char str[N];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%s",&n,&k,str+1);
        int cnt0=0,cnt1=0;
        for(int i=n;i>=1;i--){
            if(str[i]=='0')cnt0++;
            else cnt1++;
            a[i]=cnt1-cnt0;//对于每个位置求它的贡献
        }
        sort(a+2,a+n+1);//排序，注意不能包含首项
        long long sum=0,ans=1;
        bool flag=true;
        for(int i=n;i>1;i--){
            if(a[i]<=0){
                flag=false;
                break;
            }
            sum+=a[i],ans++;
            if(sum>=k)break;
        }
        if(!flag||sum<k)printf("-1\n");
        else printf("%d\n",ans);
    }
}

THE END