Description
新冠疫情非常严重，一个只有0和1的王国颁布了一项排队时的隔离措施。 排队时，两个1之间至少要有k个0。 接下来给出一些队列的样子，你要在保证隔离措施成立的情况下，把其中的一些0更换成1。 现在问你最多能更换多少个。
Input
第一行输入一个数字t，代表有t次询问。（t<=1e4) 接下来，对于每一次的询问： 第一行输入两个数字n和k，代表这个队列有多少个数字，以及两个1之间至少相隔的0的个数。(1<=k<=n<=1e5) 第二行输入一个只包含01的字符串 。
保证所有询问的n总和不超过2e5。 保证输入的01串符合隔离规则 。
Output
对于每一组询问，输出一行代表最多能把多少个0更换为1 。
Sample Input Copy
6 6 1 100010 6 2 000000 5 1 10101 3 1 001 2 2 00 1 1 0
Sample Output Copy
1 2 0 1 1 1
理解思路： //int str1=0;//指向第一个1 //int str2=s.find('1',1)//指向第二个1 //判断第一个位置if(s[0]=='0') // { // if(str2>k||str2==-1)//能否将s[0]变为1使处理更为简单 // { // ans++; // s[0]='1'; // } // } //先判断101式，最后判断10式 //9 1 //100010000 判断101式 (str2-str1-1-k)/(k+1) // 判断10式 (n-1-str1)/(k+1) #include<bits/stdc++.h> using namespace std; #define ios ios::sync_with_stdio(false); cin.tie(NULL); //const int N = 1e6+10; //代码实现： int main() { int t,n,k; cin>>t; while(t--) { cin>>n>>k; string s; cin>>s; int ans=0; int vis=0; int str1=0,str2=s.find('1',1);//1的位置 if(s[0]=='0')//判断初末位置是否为0 { if(str2>k||str2==-1) { ans++; s[0]='1'; } } if(str2==-1) { ans+=floor((n-1-str1)/(k+1)); cout<<ans<<endl; continue; } for(int i=0; i<n; i++) { if(i==str2) { ans+=floor((str2-str1-1-k)/(k+1)); str1=str2; str2 = s.find('1',i+1); } if(str2==-1) { ans+=floor((n-1-str1)/(k+1)); break; } } cout<<ans<<endl; } return 0; }