zzuli1895: 985的0-1串难题

//解法：用二分查找，如果当前位置是'1'，则查找比这个位置多k+1个零的位置，如果当前位置是'0'，则查找比当前位置多k个零的位置，

注意要在末尾添个最大的值

#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<cctype> #include<queue> #include<vector> #include<algorithm>using namespace std; typedef long long LL; #define N 100100 #define INF 0x3f3f3f3fchar s[N]; int a[N];int main() {int T, n, k, q;scanf("%d", &T);while(T--){scanf("%d%d", &n, &k);scanf("%s", s);memset(a, 0, sizeof(a));for(int i=0; i<n; i++){if(i==0&&s[i]=='1')a[i+1]=a[i-1]+1;if(s[i]=='0')a[i+1]=a[i]+1;elsea[i+1]=a[i];}a[n+1]=INF;int ans=-1;for(int i=1; i<=n; i++){if(s[i-1]=='1')q=a[i]+k+1;elseq=a[i]+k;int t=lower_bound(a, a+n+2, q)-a;ans=max(ans, t-i);}printf("%d\n", ans);}return 0 ; }

 

转载于:https://www.cnblogs.com/9968jie/p/5772184.html

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的zzuli1895: 985的0-1串难题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。