B. Vova and Trophies 字符串预处理+思维+贪心

题意：给出一个字符串只有G和S 可以交换任意两个位置的字符一次问最长的G的长度是多少

思路：预处理字符串把相同的G粘成一个G 记一下数量字符串变为 GSSGSGGSGSSG 相邻有一个S的即可粘在一起

这里要考虑字符串中有多少个部分G 假设有zz部分如果zz 大于等于3 那么两个G移动后连在一起就是 num[i]+num[j]+1 如果ZZ只有2 那就是 num[j]+num[i]

这里要考虑初始化初始化如果zz>=2 则初始化成 num[i]+1 否则就初始化成num[i] （不然会WA13 别问我为什么知道的）

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=2e5+;

 char  s[maxn],s2[maxn];

 int num[maxn];

 int main(){

     int len;

     scanf("%d",&len);

     scanf("%s",s+);

     //len=strlen(s+1);

     int flag=;

     int zz=;

     int ans=;

     for(int i=;i<=len;i++){

         if(s[i]=='G'){

             int cnt=;

             while(cnt<=len&&s[i]=='G'){

                 cnt++;

                 i++;

             }

             zz++;

             s2[flag]='G';

             num[flag++]=cnt;

             i--;

         }

         else {

             s2[flag++]='S';

         }

     }

     //for(int i=1;i<=flag-1;i++){

         //cout<<s2[i]<<" "<<num[i]<<endl;

 //    }

     for(int i=;i<=flag-;i++){

         if(zz<=)

         ans=max(ans,num[i]);

         else ans=max(ans,num[i]+);

         if(i>=&&s2[i]=='G'&&s2[i-]=='S'&&s2[i-]=='G'){

             if(zz>=)

             ans=max(ans,num[i]+num[i-]+);

             else ans=max(ans,num[i]+num[i-]);

         }

     }

     cout<<ans<<endl;

     return ;

 }

巴特西

B. Vova and Trophies 字符串预处理+思维+贪心

最新文章

热门文章