● Codeforces Round #205 (Div. 2) - D. Queue

دختر و پسرهای دبیرستانی برای سوارشدن به اتوبوس صف بسته اند، امّا اتوبوس راه می افتد اگر و تنها اگر پسرها زودتر از دخترها سوار شوند! پس باید تغییراتی در صف ایجاد شود، اینگونه که در هر ثانیه اگر پسری، دختری را جلوی خود دید جای آنها عوض می شود تا زمانی که هیچ دختری جلوی هیچ پسری نباشد؛ در اینجا دخترها را با F و پسرها را با M نمایش می دهیم. به ازای هر رشته ی ورودی شامل F و M ، حداقل زمان برای تشکیل رشته ای از تمام M ها در سمت راست و تمام F ها در سمت چپ را بر حسب ثانیه به دست آورید.

input

MMFF

output

3

input

MFMF

output

2

ورودی:

خط اوّل شامل یک رشته s1s2... sn متشکل از حروف بزرگ M و F با حداکثر سایز 10⁶ کاراکتر است که اگر si مساوی با M بود به این معنیست که نفر i-ام پسر و اگر مساوی با F بود، یعنی دختر است.

خروجی:

مدت زمان لازم برای رسیدن به یک صف ایده آل را بر حسب ثانیه به عنوان خروجی چاپ کنید. (اگر ورودی تنها شامل M و یا تنها شامل F بود، مسلماً جواب 0 خواهد بود)

// A Drop of the Programming Sea - adops.blog.ir

#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    string str="";
    cin >> str;
    int tmp=0, res=0, M=0, F=0;
    while(str[tmp]=='F' && tmp<str.length())
        tmp++;
    for(int i=tmp; i<str.length(); i++)
        if(str[i]=='F')
        {
            F++;
            res = max(res, M+F-1);
        }
        else
        {
            M++;
            F = max(0, F-1);
        }
    cout << res;
}