求助双指针(3关注
查看原帖
求助双指针(3关注
667250
Xiphi楼主2024/1/19 16:26
#include<bits/stdc++.h>
using namespace std;
int n,k;
string s;
int cg(char c){
    if(c=='J') return 1;
    if(c=='O') return 2;
    return 3;
}
bool check(){
    string t;
    int cnt=0;
    bool f[4];
    memset(f,0,sizeof f);
    for(int i=1;i<=n;++i){
        if(f[1]){
            if(f[2]){
                if(f[3]) return 1;
                else{
                    if(cnt==k) f[3]=1,cnt=0;
                    else cnt+=(cg(s[i])==3);
                    if(cnt==k) f[3]=1,cnt=0;
                    if(f[3]) return 1;
                }
            }
            else{
                if(cnt==k) f[2]=1,cnt=0;
                else cnt+=(cg(s[i])==2);
                if(cnt==k) f[2]=1,cnt=0;
            }
        }else{
            if(cnt==k) f[1]=1,cnt=0;
            else cnt+=(cg(s[i])==1);
            if(cnt==k) f[1]=1,cnt=0;
        }
    }
    return 0;
}
void solve(){
    int r=0,cnt=0,c1=0,flag=0,ss,ans=2e9,Cnt=0;
    bool f[4];
    for(int i=1;i<=n;++i){
        cnt=0,memset(f,0,sizeof f);
        Cnt=0;ss=0;
        if(cg(s[i-1])==1) flag=1;
        if(!flag||!c1||cg(s[i-1])==1){
        flag=0;
        while(r<n){
        r++;
        if(f[1]){
            if(f[2]){
                if(f[3]){ans=min(ans,Cnt);break;}
                else{
                    if(cnt==k) f[3]=1,cnt=0;
                    else cnt+=(cg(s[r])==3),Cnt+=!(cg(s[r])==3);
                    if(cnt==k){
                        ans=min(ans,Cnt);break;
                    }
                }
            }
            else{
                if(cnt==k) f[2]=1,cnt=0;
                else cnt+=(cg(s[r])==2),Cnt+=!(cg(s[r])==2);
                if(cnt==k) f[2]=1,cnt=0;
            }
        }else{
            if(cnt==k) f[1]=1,cnt=0;
            else cnt+=(cg(s[r])==1),ss|=(cg(s[r])==1),Cnt+=(ss&&(!(cg(s[r])==1)));
            if(cnt==k) f[1]=1,c1=1,cnt=0;

        }
        }
        }
        r=max(r,i);
    }
    cout<<ans;
    return ;
}
int main(){
    freopen("b.in","r",stdin);
    freopen("b.out","w",stdout);
    cin>>n>>k>>s;
    s=" "+s;
    if(!check()){
        cout<<"-1",exit(0);
    }else{
        solve();
    }
    return 0;
}

2024/1/19 16:26
加载中...