本文主要是介绍Codeforces Round #354 (Div. 2) - C. Vasya and String，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
C. Vasya and String
题目链接：http://codeforces.com/problemset/problem/676/C
Description
High school student Vasya got a string of length n as a birthday present. This string consists of letters 'a' and 'b' only. Vasya denotes beauty of the string as the maximum length of a substring (consecutive subsequence) consisting of equal letters.
Vasya can change no more than k characters of the original string. What is the maximum beauty of the string he can achieve?
Input
The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — the length of the string and the maximum number of characters to change.
The second line contains the string, consisting of letters 'a' and 'b' only.
Output
Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.
Sample Input
4 2
abba
Sample Output
4
题意：有一个只包含a和b的字符串，长度为n(n<=100000),你可以改变任意一个字符k次(0<=k<=n)，求最长的都是同一字符的字符串的长度。
题解：分别统计a和b的前缀和，前缀和的差值就是当前长度需要修改的次数，二分距离看看是否符合K次即可。
AC代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 100007;
char s[maxn];
int sum[maxn];
int n,m;
int main()
{scanf("%d%d",&n,&m);scanf("%s",s+1);int Ans = 1;int Ans2 = 1;for(int i=1;i<=n;i++){sum[i]=sum[i-1];if(s[i]=='b')sum[i]++;}for(int i=1;i<=n;i++){int ans = 0;int l = i;int r = n;while(l<r){int mid = (l+r+1)/2;if(sum[mid]-sum[i]<=m){l=mid;}else r = mid - 1;ans = l;}if(sum[ans]-sum[i-1]<=m)Ans = max(ans-i+1,Ans);else Ans = max(ans-i,Ans);}//printf("%d",Ans);for(int i=1;i<=n;i++){sum[i]=sum[i-1];if(s[i]=='a')sum[i]++;}for(int i=1;i<=n;i++){int ans = 0;int l = i;int r = n;while(l<r){int mid = (l+r+1)/2;if(sum[mid]-sum[i]<=m){l=mid;}else r = mid - 1;ans = l;}if(sum[ans]-sum[i-1]<=m)Ans2 = max(ans-i+1,Ans2);else Ans2 = max(ans-i,Ans2);}// printf("%d",Ans2);printf("%d\n",max(Ans2,Ans));return 0;
}这篇关于Codeforces Round #354 (Div. 2) - C. Vasya and String的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
