P9644 题解

Dws_t7760 · 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;
}