[C++知识库]C. Vasya and String（cf）前缀和 + 二分答案

原题链接：Problem - 676C - Codeforces

题目大意：给你一串字符串，只包含a和b两个小写字母。子串的长度是n，然后给了你一个数k，这是你能改变字母的最大个数，然后求改变后能获得的最大连续子串长度是多少。

思路：

1.这个题可以用二分来做，二分最大长度，然后每次判断在这个最大长度之下连续子串能不能由改变至多k个字母获得；

2.这里可以用到前缀和做预处理，把a出现的地方看成1，b看成0，那么选定了一个最大子串长度x，就顺序查找每一个这样长度子串中，把所有字母变成a或b能不能在k步之内实现。

AC代码：?

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ios ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef pair<int, int> PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))
 
const int N = 1e5 + 10;
char a[N];
int s[N]; //a数量的前缀和
int n, k;
 
bool check(int x){
    rep(i, n - x + 1){
        int j = i + x - 1;
        if(s[j] - s[i - 1] <= k || x - (s[j] - s[i - 1]) <= k) return true;
    }
    return false;
}
 
int main(){
    scanf("%d %d", &n, &k);
    scanf("%s", a + 1);
    rep(i, n) s[i] = (a[i] == 'a'), s[i] += s[i - 1];
    int l = 1, r = n;
    while(l < r){
        int mid = l + r + 1 >> 1;
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    printf("%d", l);
    return 0;
}

?