自动搬运

查看原文

来自洛谷，原作者为

	jinhangdong 支持互关，有勾就行

搬运于2025-08-24 23:08:26，当前版本为作者最后更新于2025-01-11 19:08:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

二分答案，每次看看至少需要分成几块 $\le k$ 就移右端点，否则移左端点。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int l,r=1e18,n,k;
string s;
bool check(int x)
{
	int cnt=1,c1=0,c0=0;
	for(int i=1;i<=n;++i)
	{
		if(s[i]=='1') c1++;
		else c0++;
		if(c1*c0>x)//说明需要新的块
		{
			cnt++;
			c1=0,c0=0;
			if(s[i]=='1') c1++;
			else c0++;
		}
	}
	return cnt<=k;
}
signed main()
{
	cin>>n>>k;
	cin>>s;
	s=" "+s;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	cout<<r;
	return 0;
}