题目描述：
It's already 21:30 now, and it's time for BaoBao to go to bed. To ensure his sleeping quality, BaoBao decides to turn all the lights in his bedroom off.
There are n lights, numbered from 1 to n, arranged in a row in BaoBao's bedroom. Each time BaoBao can select an integer i and turn all the lights numbered from i to (i+L−1) (both inclusive) off, where L is a predefined positive integer. Note that each time the value of L must be the same.
Given the initial status of all the lights, please help BaoBao determine the smallest possible L so that he can turn all the lights off within k times.
Input
There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:
The first line contains two integers n and k (1≤k≤n≤2×105).
The second line contains a string s (|s| = n s∈{’0’,’1’}) indicating the initial status of the lights. Let s[1] be the i-th character in s, if s[i]=’1’ then the i-th light is initially on, otherwise it's initially off. It's guaranteed that there is at least one '1' in s.
It's guaranteed that the sum of n of all test cases will not exceed 2×1e6.
Output
For each test case output one line containing one integer, indicating the smallest possible L.
Sample
Input
2
10 4
0101011111
3 1
010
Output
3
1Time limit
1000 ms
Mem limit
65536 kB
OS
Linux
Author
CHEN, Jingbang
Spoilers
Hide
题目大意：给你一个字符串s，让你在k次操作内将字符串内所有的1变成0，每次操作会使[i,i+L-1]内的1变成0，我们要求最小的L
思路分析：通过二分搜索可能的L取值，最后会得到一个L的取值区间，所以结果就是区间的左端点，具体见代码。
代码：
#include<iostream>
using namespace std;
int main() {int t;cin>>t;while(t--){int n, k;scanf("%d%d", &n, &k);string a;cin >> a;int l=1,r=n;//L可能的取值在[1,n] while(l<r){int mid=(l+r)/2;int ans=0;for(int i=0;i<n;i++){if(a[i]=='0')continue;//如果a[i]为1，我们就进行一次操作，使得[i,i+mid-1]区间范围内的1全部变成0 i=i+mid-1;//跳过已经处理的范围 ans++;//操作次数+1 }if(ans<=k)//操作次数满足条件，去找更小的L {r=mid;}elsel=mid+1;}cout<<l<<endl;}
}有用的英文单词：both inclusive 都包括在内 initial 最初的
