CF353D Queue

思维好题：

（大胆猜想加验证！！！）

首先排在最前面的女生们是不需要移动的。而对于后面每一个女生，若前面一个到达指定位置时间为t，则如果其紧跟其后，其时间为t+1。譬如：MFF>FMF>FFM。

若不能紧跟其后，则其时间等于在其前面的男生（总是会退回来被她交换，若不能及时交换而卡在原地，则必定有一个F挡在其前面，前面不是F就是M）所以每个人时间为max(ans+1，cnt）（cnt为男生数）。//对于这种两个量以及类似的题，可以讨论其前面不是变量1就是变量2（高度总结）

上代码：

 1 #include<bits/stdc++.h>
 2 #define maxn 1000005
 3 using namespace std;
 4 char s[maxn];
 5 void init(){
 6     scanf("%s",s+1);
 7     int ans=0;
 8     int pos=1;
 9     int cnt=0;
10     while(s[pos]=='F') pos++;
11     for(int i=pos;s[i];i++){
12         if(s[i]=='M') cnt++;
13         else{
14             ans=max(ans+1,cnt);
15         }
16     }
17     printf("%d",ans);
18 } 
19 int main(){
20     init();
21     
22     return 0;
23 }