午餐时间还未到,饥饿的程序员们早早就在食堂门口排队了。

假设现在的队列是这样的:MFM。

从左往右,第一位是男程序员(Male),第二位是女程序员(Female),第三位是一位男程序员。

但是男程序员不会让女程序员排在他们后面,于是就会发生这样的情况:只要一位男程序员发现自己后面是一位女程序员,他就会和这位女程序员交换位置,这样的交换需要消耗一秒。

当然,在同一秒内可能会有多位男程序员和自己后面的女程序员交换位置。

现在,请问最少要消耗多长时间,队伍不再变动。

输入格式

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

输出格式

队伍不再变动的时间。

数据范围

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

输入样例:

 MMFF

输出样例:

 3

题目分析

贪心

假设第 iF需要交换的次数 < 她前面的男生的数目, 可知她的前面一定还会存在男生,不满足题意。则 她需要交换的次数 >= 她前面的男生的数目。 假设第 iF需要交换的次数 < 她前面的女生需要交换的次数 +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;
}
分类: Thought

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status