自动搬运

查看原文

来自洛谷，原作者为

	Dws_t7760 AH 在役蒟蒻 OIer || 此时此刻的光辉，盼君勿忘 || 每日一% @Hu_taooo || 最后在线时间：2025年8月24日21时31分

搬运于2025-08-24 22:50:22，当前版本为作者最后更新于2023-09-17 18:33:44，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道二分题。

由于数据保证至少有一个盏灯是开的，我们可以在 $1$ 和 $n$ 之间二分查找答案。

二分思路：假设每次操作可以将连续的 $L$ 盏灯关掉，我们从左到右依次遍历所有灯，如果是关的，就跳过，否则如果操作次数没有达到 $k$，将从这盏灯开始的连续 $L$ 盏灯关掉。最后如果所有的灯都关掉了，那么这个 $L$ 就满足条件。我们在 $1$ 和 $n$ 之间二分查找答案，最后找出最小的满足条件的 $L$ 作为答案。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
int t,n,k,l,r,mid,ans;
string a;
bool check(int ll) {
	string temp=a;
	int s=0,i=0;
	while(i<n) {
		if(temp[i]=='0') {
			i++;
			continue;
		}
		for(int j=i;j<min(i+ll,n);j++) temp[j]='0';
		i+=ll,s++;
		if(s>=k) break;
	}
	for(i=0;i<n;i++) if(temp[i]=='1') return 0;
	return 1;
}
int main() {
	ios::sync_with_stdio(0),cin.tie(0),cout.tie();
	cin>>t;
	for(int i=0;i<t;i++) {
		cin>>n>>k;
		cin>>a;
		l=1,ans=r=n;
		while(l<=r) {
			mid=(l+r)/2;
			if(check(mid)) ans=mid,r=mid-1;
			else l=mid+1;
		}
		cout<<ans<<endl;
	}
	return 0;
}