Codeforces 1082 B. Vova and Trophies-有坑 (Educational Codeforces Round 55 (Rated for Div. 2))
2 seconds
256 megabytes
standard input
standard output
Vova has won nn trophies in different competitions. Each trophy is either golden or silver. The trophies are arranged in a row.
The beauty of the arrangement is the length of the longest subsegment consisting of golden trophies. Vova wants to swap two trophies (not necessarily adjacent ones) to make the arrangement as beautiful as possible — that means, to maximize the length of the longest such subsegment.
Help Vova! Tell him the maximum possible beauty of the arrangement if he is allowed to do at most one swap.
The first line contains one integer nn (2≤n≤1052≤n≤105) — the number of trophies.
The second line contains nn characters, each of them is either G or S. If the ii-th character is G, then the ii-th trophy is a golden one, otherwise it's a silver trophy.
Print the maximum possible length of a subsegment of golden trophies, if Vova is allowed to do at most one swap.
10
GGGSGGGSGG
7
4
GGGG
4
3
SSS
0
In the first example Vova has to swap trophies with indices 44 and 1010. Thus he will obtain the sequence "GGGGGGGSGS", the length of the longest subsegment of golden trophies is 77.
In the second example Vova can make no swaps at all. The length of the longest subsegment of golden trophies in the sequence is 44.
In the third example Vova cannot do anything to make the length of the longest subsegment of golden trophies in the sequence greater than 00.
在左右两侧都是G,中间为S的时候,在最后需要和直接连续G的长度交换一个S为G的比较一下,wa在这里了。
代码:
//B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+;
const int inf=0x3f3f3f3f; char c[maxn];
vector<int> ve; int main()
{
int n;cin>>n;
cin>>c;
int num=;
for(int i=;i<n;i++){
if(c[i]=='G') num++;
if(c[i-]=='G'&&c[i]=='S'&&c[i+]=='G') ve.push_back(i);
}
int ret=,tmp=;
for(int i=;i<n;i++){
if(c[i]=='G') tmp++;
else ret=max(ret,tmp),tmp=;
}
ret=max(ret,tmp);
ret=min(ret+,num);
if(num==n) {cout<<n<<endl;return ;}
if(num==) {cout<<<<endl;return ;}
if(ve.size()==){
int ans=-,cnt=;
for(int i=;i<n;i++){
if(c[i]=='G') cnt++;
if(c[i]=='S') ans=max(ans,cnt),cnt=;
}
ans=max(ans,cnt);
cout<<min(num,ans+)<<endl;
}
else{
int ans=,flag=;
for(auto it:ve){
int cnt=;
for(int i=it-;i>=;i--){
if(c[i]=='S') break;
else cnt++;
}
for(int i=it+;i<n;i++){
if(c[i]=='S') break;
else cnt++;
}
ans=max(ans,cnt);
}
ans=min(num,ans+);
cout<<max(ans,ret)<<endl;
}
} /*
16
GSGSSGSSGGGSSSGS 4
*/
最新文章
- Centos7搭建需要mysql的网站
- WinPipe后门程序代码示例(仅限技术交流)
- mongodb python image 图像存储读取
- Git初使用
- Spark Programming--Transformations
- Hbase常用命令
- 深入浅出ES6(三):生成器 Generators
- Apache的多路处理模块MPM:Prefork Worker Event
- 用dup2和dup产生一份file descriptor 的拷贝
- PCB抄板评估需要关注的因素
- Bash命令行编辑
- Java笔试题库之选题题篇【1-70题】
- 又拍云张聪:OpenResty 动态流控的几种姿势
- MyRolan (快速启动小工具)
- web容器 web服务器 servlet/jsp容器 之间的区别和关系
- AIS系统(转)
- zsh:no matches found 问题解决
- redis 过期时间与缓存
- Vue v-if 和 v-show
- 【基于初学者的SSH】struts2 值栈的详解与struts2标签库+ognl表达式
热门文章
- Linux下find命令及其参数的使用
- 【Android】完善Android学习(三:API 3.0)
- [bzoj1002]轮状病毒-矩阵树定理
- hdu 1070 Milk(贪心)
- 3.0docker操作
- perl HTML::LinkExtor模块(2)
- sicily 1016. 排队接水--课程作业
- iOS一个项目开始创建, 部署到git服务器
- VPS性能测试方法小结(8)
- [bugfix]copy属性参数将NSMutableArray变为NSArray类型