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 别问我为什么知道的）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2e5+6;
 4 char  s[maxn],s2[maxn];
 5 int num[maxn];
 6 int main(){
 7     int len;
 8     scanf("%d",&len);
 9     scanf("%s",s+1);
10     //len=strlen(s+1);
11     int flag=1;
12     int zz=0;
13     int ans=0;
14     for(int i=1;i<=len;i++){
15         if(s[i]=='G'){
16             int cnt=0;
17             while(cnt<=len&&s[i]=='G'){
18                 cnt++;
19                 i++;
20             }
21             zz++;
22             s2[flag]='G';
23             num[flag++]=cnt;
24             i--;
25         }
26         else {
27             s2[flag++]='S';
28         }
29     }
30     //for(int i=1;i<=flag-1;i++){
31         //cout<<s2[i]<<" "<<num[i]<<endl;
32 //    }
33     
34     for(int i=1;i<=flag-1;i++){
35         if(zz<=1)
36         ans=max(ans,num[i]);
37         else ans=max(ans,num[i]+1);
38         if(i>=3&&s2[i]=='G'&&s2[i-1]=='S'&&s2[i-2]=='G'){
39             if(zz>=3)
40             ans=max(ans,num[i]+num[i-2]+1);
41             else ans=max(ans,num[i]+num[i-2]);
42         }
43     }
44     cout<<ans<<endl;
45     return 0;
46 }

View Code