CF676C Vasya and String

Ideas

Similar to the simple rule taking method , Separate the sequence with a,b To calculate .

To choose a Come on , We treat each b assignment 1 Representative needs 1 The price to get 1 The value of , Yes a The price is 0, This problem turns into a simple rule taking method .( At the greatest cost k The longest number of sequences can be obtained even if the answer ). Then on b Do the same thing , The answer is to take the maximum of two operations .

Code

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
int a[maxn];
int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int cnt=0,n,k;
    string ss;
    cin>>n>>k>>ss;
    int ans=0;
    int s=1,w=0,sum=0;
    a[1]=ss[0]=='a'?1:0;// Assign a value to the initial cost 
    for(int i=1;i<n;i++){
    
        a[i+1]=(ss[i]=='a'?1:0);// Pretreatment cost 
    }
    for(int i=1;i<=n;i++){
    // Simple ruler method 
        sum++;w+=a[i];
        while(s<=i&&w>k){
    // cost w, Maximum price to pay k
            sum--;w-=a[s++];
        }
        ans=max(ans,sum);
    }
    a[1]=ss[0]=='b'?1:0;// ditto 
    for(int i=1;i<n;i++){
    
        a[i+1]=(ss[i]=='b'?1:0);
    }
    s=1,sum=0,w=0;
    for(int i=1;i<=n;i++){
    
        sum++;w+=a[i];
        while(s<=i&&w>k){
    
            sum--;w-=a[s++];
        }
        ans=max(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}