Description

985有一個長度為n的0-1串，已知他最多可以修改k次（每次修改一個字符即0->1 或者 1->0），他想知道連續的全1子串最長是多少。

?

Input

第一行輸入一個整數t，代表有t組測試數據。 每組數據第一行輸入兩個整數n，k分別代筆上面的信息。 注：1 <= t <= 12，1 <= n <= 100000，0 <= k <= 100000。

?

Output

一個整數代表可以得到的最大長度。

?

Sample Input

2 6 3 010100 6 2 010100

Sample Output

5 4 重新的理解了 二分函數 ? 感覺挺重要的 ? ?光為了理解那個函數的意思就編譯了好久 ? 不過最后還是 ?寫了出來 q=upper_bound(sum,sum+len,sum[i]-s+n)-sum; 好比（1,2,2,4） upper_bound（2）==3；3表示的是下標? 也就是數字4的位置 q=lower_bound(sum,sum+len,sum[i]-s+n)-sum;好比（1,2,2,4） lower_bound（2）==1；1表示的是下標? 也就是第一個數字2的位置 #include<algorithm> #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<math.h> using namespace std; #define INF 0x3f3f3f3f #define N 102311 int sum[N],dp[N]; char str[N]; int main() {/*int a[123]={1,1,1,2,2,2,3,4};寫這些主要是為了編譯二分函數 int n=8,w;while(scanf("%d",&w)!=EOF){int q=upper_bound(a,a+n,w)-a;printf("%d\n",q);}*/int T,len,n;scanf("%d",&T);while(T--){sum[0]=0;scanf("%d%d%s",&len,&n,str);for(int i=0;i<len;i++){if(i==0){if(str[i]=='0')sum[i]=1;elsesum[i]=0;continue;}if(str[i]=='0')sum[i]=sum[i-1]+1;elsesum[i]=sum[i-1];}int ans=0;for(int i=0;i<len;i++){int s;if(str[i]=='0')s=1;else s=0;int q=upper_bound(sum,sum+len,sum[i]-s+n)-sum;dp[i]=q-i;ans=max(ans,dp[i]);///printf("%d\n",dp[i]); }printf("%d\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/a719525932/p/5735634.html

總結

以上是生活随笔為你收集整理的http://acm.zzuli.edu.cn/zzuliacm/problem.php?id=1895 二分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。