景女神与她的托福
Problem Description 景女神最近一直在恶补英语，她要为了她的托福做准备。于是，满神给景女神出了一道题，来帮助景女神学习英语。 满神给了景女神一个长度为n的字符串，字符串只包含小写字母 a,b;并且告诉景女神她最多可以改变k个字符(a->b, b->a);满神想知道经过不超过k次的改变后，出现相同字母的字符串(连续)的最大长度是多少。 景女神觉得这个题和她记单词并没有什么关系，于是就学英语去了。但是满神希望聪明的你可以帮助他解决这个问题。
Input 多组输入，每组输入如下 第一行输入两个整数n和k，用空格隔开 (1 <= n <= 100000, 0 <= k <= n); 第二行输入一个字符串。(只包含小写字母 a和b);
Output 多组输出，每组输出一个整数，表示经过不超过k次改变后，出现相同字符的最大字符串长度。
Sample Input 4 2 abba 8 1 aabaabaa
Sample Output 4 5
Hint: 第一组样例：可以得到 aaaa 或者 bbbb;最大长度为4; 第二组样例：可以得到 aaaaabaa 或者 aabaaaaa; 最大长度的字符串是 aaaaa，长度为5;
思路，不是全部转化成a就是转化成b，然后取这两种情况中的最大值即可。用一个数组来存位置。
代码如下
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<cmath> #include<string> #define inf 1<<30 #define eps 1e-7 #define LD long double #define LL long long #define maxn 1000000005 #define p 3.1415926 #define N 100005 #define IO ios_base::sync_with_stdio(0),cin.tie(0)//加快cin的读入速度 using namespace std; int n,k,q[N]; string s; int main() { IO; while(cin>>n>>k){ cin>>s; int ans,head,tail,st; ans=head=tail=st=0; for(int i=0;i<=s.size()-1;i++)//改b { if(s[i]=='b') //如果是b q[tail++]=i; //记录第tail+1个b的位置 if(tail-head>k) //如果改变的b的数量大于k st=q[head++]+1;//最左边的b不改变，空出一个改变的次数 ans=max(ans,i-st+1); //此时的a串长度即为i-st+1 } head=tail=st=0; for(int i=0;i<=s.size()-1;i++)//改a ，同上 { if(s[i]=='a') q[tail++]=i; if(tail-head>k) st=q[head++]+1; ans=max(ans,i-st+1); } cout<<ans<<endl; } return 0; }