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 0x3f3f3f3f

char 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;
            else
                a[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;
            else
                q=a[i]+k;
            int t=lower_bound(a, a+n+2, q)-a;
            ans=max(ans, t-i);
        }
        printf("%d
", ans);
    }
    return 0 ;
}