Black & White 题解

https://ac.nowcoder.com/acm/contest/893/F?&headNav=acm

题目链接在上

题意：给一串n位长度的0，1字符串，允许最多m次修改，即0改成1，1改成0，问：最终最长的连续相同的字符串可以是多少长度？

样例解读：
5 1
00101
长度为5，修改1次，即把1改成0，变成00001，答案是4
2 1
01
长度为2，修改1次，这就随便了，1改成0，或者0改成1，变成00，或11，答案是2

思路：
要求最长，换个思路：告诉你有一段连续相同的字符串长度为x，能否在m次修改里，判断成功与否？
可以。前缀和+for循环判断
题意再转换：最长 即 x 最大
二分。

前缀和：zero[ed] - zero[st - 1]表示 从[st, ed] 区间共有多少 0
二分：标准框架

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 20;
int zero[maxn];
int one[maxn];
char s[maxn];
    int T, n, m;

int calc(int x){
    for(int st = 1; st + x - 1 <= n; st ++){
        int ed = st + x - 1;
        if (zero[ed] - zero[st - 1] <= m) return 1;
        if (one[ed] - one[st - 1] <= m) return 1;
    }
    return 0;
}

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &m);
        scanf("%s", s + 1);
        //printf("%s\n", s + 1);
        memset(zero, 0, sizeof(zero));
        memset(one, 0, sizeof(one));
        for(int i = 1; i <= n; i++)
            if (s[i] == '0'){
                zero[i] = zero[i - 1] + 1;
                one[i] = one[i - 1];
            }
            else{
                one[i] = one[i - 1] + 1;
                zero[i] = zero[i - 1];
            }
        //for(int i = 1; i <= n; i++)
        //    printf("%d%c", zero[i], i==n ? '\n' : ' ');
        //for(int i = 1; i <= n; i++)
        //    printf("%d%c", one[i], i==n ? '\n' : ' ');
        int l = 0;
        int r = n;
        int mid, ans;
        while(l <= r){
            mid = (l + r) >> 1;
            if (calc(mid)){
                l = mid + 1;
                ans = mid;
            }
            else r = mid - 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}