CF353D Queue

题目简述

给定一个长度不超过 $10^6$ 的，由 M 和 F 组成的字符串。每秒可以做若干次这样的操作：选择一个 F，如果它的前面是 M 那么交换这两个字符（每一个 F 每一秒只能被操作一次）。多少秒后所有的 F 都在最前面？

思路

因为每一个 F 每一秒只能被操作一次，对于一个 F，要到最前面需要它前面的 M 的个数秒。因为每秒钟可以进行的操作次数没有限制所以不同的 F 操作可以叠加：考虑一个 F，如果它之前是一个 F，那么它只需要上一个 F的时间加一（因为每次上一个 F 交换来的 M 它都可以操作）。每次拿当前 M个数和上一个F的答案去最小值即可。

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<climits>
#define int long long
using namespace std;
const int MaxN = 1000006;
char str[MaxN];

signed main(){
	scanf("%s", str+1);
	int len = strlen(str+1);
	int ans = 0, danshi = 0;
	for(int i=1; i<=len; i++){
		switch(str[i]){
			case 'M':{
				danshi++;
				break;
			}
			case 'F':{
				if(danshi > 0) ans = max(ans+1, danshi);
				break;
			}
		}
	}
	printf("%lld", ans);
	return 0;
}