CF353D Queue 题解

题意概述

F 代表女生，M 代表男生。 每次如果男生在女生左边，调换男女生位置。直到所有女生都在男生的左边。

很显然，每秒钟不止一个女生可以换位置。（如 样例 2）

思路

思路 1 （TLE on #8）

模拟每一秒调换，直到满足要求。

#include<bits/stdc++.h>
using namespace std;
string str;
int times;
bool check() {
	bool flag=false;
	for(register int i=0;i<str.size();i++) {
		if(str[i]=='M') flag=true;
		if(str[i]=='F'&&flag) return false; 
	}
	return true;
}
int main() {
	cin>>str;
	while(!check()) {
		for(register int i=str.size()-1;i>=0;i--) {
			if(str[i]=='F'&&i!=0) {
				if(str[i-1]=='M') {
					swap(str[i],str[i-1]);
					i--;
				}
			}
		}
		times++;
	}
	cout<<times;
	return 0;
}
//code by TheCedar

这个代码的最坏时间复杂度是 $O(n^2)$。一看看数据限制： $1 \leqslant n \leqslant 1 \times 10^6$ 。显然超时。

这里具体坑点也不说了，反正过不了。

思路 2 （AC）

既然要让所有女生换到最左边，与其枚举每一秒，还不如让每一个女生一次直接换到最左。

当然，如果有一个女生在这个女生的左边且两个女生在一起。那么后者将会在前者后 1 秒到达左边。

反之，如果一个女生左边相邻位置没有女生，那么她到达最左边就是前面男生的个数。

重要的一点： 在这些女生到达最左边的时间里，应该取最大值。

因为每秒，所有可以调换位置的女生都可以进行调换，所以在最后一个女生到达最左边时，其他女生已经到达。

变量说明

设某女生前男生个数为 $cnt$，我们每扫到一个男生就 cnt++ 即可。

设最后一个女生到达左边的时间为 $times$。

代码实现

#include<bits/stdc++.h>
using namespace std;
string str;
int cnt,times;
int main() {
	cin>>str;
	for(int i=0;i<str.size();i++) {
		if(str[i]=='M') cnt++;
		if(str[i]=='F'&&cnt>0) times=max(times+1,cnt);
	}
	printf("%d",times);
	return 0;
}
//code by TheCedar

时间复杂度 $O(n)$，轻松过掉此题。