（模拟题）B. Vova and Trophies—— Educational Codeforces Round 55 (Rated for Div. 2)

悠悠 2022-04-13 14:19 231阅读 0赞

传送门：B. Vova and Trophies

题意：给你一个长度为n且只由’G’，’S’组成的字符串，’G’，’S’的位置最多互换一次，问连续’G’的最大长度？

思路：看到题目，感觉O(n)的时间复杂度就能实现，时限2s，足够了。设置cnt1,cnt2分别存取一个’S’左右的连续的‘G’的最大长度。

注意：

  • 遍历的时候，遇到一个’S’，那么它前一个’S’，’GGSGG’这种情况就可以处理了，同时更新最终答案mx，假设这个序列中存在多余的‘G’和它互换，mx=max(mx,cnt1+cnt2+1)，其中的1，表示互换得来的’G’；
  • 遍历到最后，别忘了再次更新mx；

  • 那到底有没有多余的’G’和’S’互换呢？咱们就求出整个序列的’G’的个数，最后与mx进行比较取较小的那个。（比赛过程中就漏了这个情况，导致没能AC）。

    include

    include

    include

    include

    using namespace std;
    typedef long long ll;
    char str[100010];
    int n;

    int solve(){

    1. int mx=0,cnt1=0,cnt2=0,tag=0;
    2. for(int i=0;i<n;i++){
    3.     if(str[i]=='S'){
    4.         tag++;
    5.         mx=max(mx,cnt1+cnt2+1);
    6.         cnt1=cnt2;
    7.         cnt2=0;
    8.     }else{
    9.         cnt2++;
    10.     }
    11. }
    12. mx=max(mx,cnt1+cnt2+1);
    13. mx=min(mx,n-tag);
    14. return mx;

    }

    int main(){

    1. while(~scanf("%d",&n)){
    2.     scanf("%s",str);
    3.     printf("%d\n",solve());
    4. }
    5. return 0;

    }

发表评论

表情：
评论列表 （有 0 条评论，231人围观）

还没有评论，来说两句吧...

相关阅读