这一题考虑单调栈，我们用x[i]表示前i个字符串全部变成元音字母的代价，然后枚举以每一个字符开头，看其能够扩展的那个地方。
我们比如说
henghengeaaaa 3
x[ ]={1,1,2,3,4,4,5,6,6,6,6,6,6}
以第5个字符开始，不算上自己，因为可能自己就需要用掉一次修改的机会。
所以其最远能扩展的就是第一个大于x[5-1]+k的下标减去5这个起始字符，在加一。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #define N 1000012 using namespace std; int sum[N]; char str[N]; int main() { int i,n,t,k,s,ans; scanf("%dn",&t); while(t--) {ans=0; scanf("%s %dn",str+1,&k);n=strlen(str+1);for(i=1;i<=n;++i){if(str[i]=='a'|| str[i]=='e'|| str[i]=='i'|| str[i]=='o'|| str[i]=='u')sum[i]=sum[i-1];else sum[i]=sum[i-1]+1;}if(sum[n]<=k){printf("%dn",n);continue;}for(i=1;i<=n;++i){s=upper_bound(sum+1,sum+n+1,sum[i-1]+k)-sum-1;ans=max(ans,s-i+1); if(sum[n]-sum[i-1]<=k)break;}printf("%dn",ans);} return 0; }
12345678910111213141516171819202122232425262728293031323334353637
