(模拟题)B. Vova and Trophies—— Educational Codeforces Round 55 (Rated for Div. 2)
程序员文章站
2022-03-14 19:48:26
...
题意:给你一个长度为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<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
char str[100010];
int n;
int solve(){
int mx=0,cnt1=0,cnt2=0,tag=0;
for(int i=0;i<n;i++){
if(str[i]=='S'){
tag++;
mx=max(mx,cnt1+cnt2+1);
cnt1=cnt2;
cnt2=0;
}else{
cnt2++;
}
}
mx=max(mx,cnt1+cnt2+1);
mx=min(mx,n-tag);
return mx;
}
int main(){
while(~scanf("%d",&n)){
scanf("%s",str);
printf("%d\n",solve());
}
return 0;
}
推荐阅读
-
Educational Codeforces Round 55 (Rated for Div. 2) D. Maximum Diameter Graph (构造图)
-
Educational Codeforces Round 49 (Rated for Div. 2) B. Numbers on the Chessboard
-
Educational Codeforces Round 49 (Rated for Div. 2) B. Numbers on the Chessboard
-
B. RPG Protagonist[Educational Codeforces Round 94 (Rated for Div. 2)]数学枚举
-
Educational Codeforces Round 52 (Rated for Div. 2)B. Vasya and Isolated Vertices
-
Educational Codeforces Round 52 (Rated for Div. 2) B. Vasya and Isolated Vertices
-
Educational Codeforces Round 53 (Rated for Div. 2) B. Vasya and Books
-
Educational Codeforces Round 52 (Rated for Div. 2) B. Vasya and Isolated Vertices
-
(模拟题)B. Vova and Trophies—— Educational Codeforces Round 55 (Rated for Div. 2)
-
Educational Codeforces Round 52 (Rated for Div. 2)B. Vasya and Isolated Vertices·「模拟,思维」