B. Vova and Trophies

链接

[https://codeforces.com/contest/1082/problem/B]

题意

给你一个包含GS的字符串，只允许交换一次任意不同位置的字符，问最长的连续G串是多少

分析

很显然贪心找相邻的中间间隔一个S的两个连续G串

看了别人写的很巧妙，多用几个样例就知道其中的奥妙了

代码

#include<bits/stdc++.h>

using namespace std;

int main(){

	int n; string s;

	//freopen("in.txt","r",stdin);

	while(cin>>n){

		cin>>s;

		int cntG=0,cntS=0,sumG=0,ans=0;

		for(int i=0;i<n;i++){

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

				cntG++; sumG++;

			}

			else{

				cntS=cntG; cntG=0;//遇到scntG从新归零统计G连续的个数

			}

			ans=max(ans,cntG+cntS+1);//假设都可以交换带来收益

		}

		ans=min(ans,sumG);//这里很关键存在交换没有带来收益的

		cout<<ans<<endl;

	}

	return 0;

}

巴特西

B. Vova and Trophies

链接

题意

分析

代码

最新文章

热门文章