Codeforces 353D Queue（构造法）
【题目链接】 http://codeforces.com/contest/353/problem/D
【题目大意】
10^6个男女排队，每一秒，如果男生在女生前面，即pos[i]是男生，pos[i+1]是女生，两人互换位置，求解在多少秒后，队伍不再变化。
【题解】
对于前后的两个女生来说，如果后面的女生在前移的过程中会碰到前面的女生，那么它所需要的时间就是前面女生所需要的时间+1，那么从前到后统计，不断更新最大值即可。
【代码】
#include <cstdio>
#include <algorithm>
using namespace std;
int pos,ans,n;
char s[1000005];
int main(){
scanf("%s",s);
for(ans=pos=0;s[pos]=='F';pos++);
for(int i=pos;s[i]!='\0';i++){
if(s[i]=='M')n++;
else ans=max(ans+1,n);
}return printf("%d\n",ans),0;
}
评论 (0)
