女士优先-南京理工大学

2023 年 08 月 06 日

437 次浏览

1156字数

[来自KeChang](https://blog.silvery.me/)

> 午餐时间还未到，饥饿的程序员们早早就在食堂门口排队了。
> 
> 假设现在的队列是这样的：MFM。
> 
> 从左往右，第一位是男程序员（Male），第二位是女程序员（Female），第三位是一位男程序员。
> 
> 但是男程序员不会让女程序员排在他们后面，于是就会发生这样的情况：只要一位男程序员发现自己后面是一位女程序员，他就会和这位女程序员交换位置，这样的交换需要消耗一秒。
> 
> 当然，在同一秒内可能会有多位男程序员和自己后面的女程序员交换位置。
> 
> 现在，请问最少要消耗多长时间，队伍不再变动。

### 输入格式

输入一个字符串，仅包含 M 和 F 两种字母，表示当前的排队情况。

### 输出格式

队伍不再变动的时间。

### 数据范围

输入字符串长度不超过 105 。

### 输入样例：

```
MMFF
```

### 输出样例：

```
3
```

### 题目分析

贪心

假设第 `i` 个 `F`需要交换的次数 < 她前面的男生的数目， 可知她的前面一定还会存在男生，不满足题意。则 她需要交换的次数 >= 她前面的男生的数目。
假设第 `i` 个 `F`需要交换的次数 < 她前面的女生需要交换的次数 +1，若 两女生的编号为 `i`,`i - 1`，若第 `i` 个女生需要交换的次数 < 第`i - 1`个女生需要交换的次数 +1，很明显，假设不成立。所以她需要交换的次数 >= 她前面的女生需要交换的次数 + 1。

综上可知 第 `i 个 F 需要交换的次数 = max (她前面的女生需要交换的次数 +1, 她前面的男生的数目)`。

### 代码实现

```
#include <iostream>
using namespace std;
const int N = 0;

int p, cnt, dp[N], t;
string s;
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    while(p < (int)s.length() && s[p] == 'F') ++p;
    while(p < (int)s.length()) {
        if (s[p] == 'M') ++cnt;
        else t = max(t + 1, cnt);
        ++p;
    }
    cout << t;
    return 0;
}
```

最后修改：2023 年 08 月 06 日