排队时间仅由最后一个排好的时间确定

最后一个女最少要花费a[i],a[i]表示前缀的男生数目

但最后一个女生可能会被前面的一个女生暂时堵住。

所以此时还要维护一个wait记录等待前方女生让路时间。

那么，答案就是等待时间加上前面男生数目 wait + a[i]

考虑如何维护wait

显然第一个女生不用等 wait = 0

第二个女生如果和第一个女生紧挨 需要等一秒 ，wait ++

如果第二个女生和第一个中间每有男生，

第二个女生可以先往前走，直到走完中间男生

此时如果前面还有女生没排好，再等

可以发现，每有一个男生，可以少等一次 wait –

令，wait不能为负

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int a[100010];
int main() {
    string str;
    cin >> str;
    int N = str.size();
    int ans = 0;
    int wait = 0;
    for(int i = 1;i <= N;i ++) {
        a[i] = a[i - 1];
        if(str[i - 1] == 'M') {
            a[i] ++;
            wait = max(wait - 1,0);
        }else {
            ans = max(wait + a[i],ans);
            wait ++;
        }
    }

    cout << ans << endl;
}