题解 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

，将序列分成三段。

程序如下：

CPP

#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

相关推荐

评论

题解 CF2042C