TRZ_2007 的博客

TRZ_2007 的博客

题解 AT2059 【STring】

posted on 2019-06-22 10:54:19 | under 题解 |

Solution

这道题目初看的时候可能一点思路都没有,因为它需要删除字符,让我们想起了消灭星星,但是我们可以这么反过来想,我们可以统计字符 $S$ 出现的次数,在字符 $S$ 有出现的前提下,如果出现了 $T$ ,那么就丢出一个 $S$ 来和 $T$ 匹配,需要删除的数量自加2,最后把总长度减去删除长度就可以了,注意,AT题需要换行!!!

$code$

#include <bits/stdc++.h>
using namespace std;

string S;
int sums,sumt;

int main()
{
    cin>>S;
    for(int i=0;i<S.size();i++)
    {
        if(S[i] == 'S') sums++;//有S,S出现的次数++
        if((sums)&&(S[i]=='T'))//在有S的前提下,有T
        {
            sums--;//丢出一个S
            sumt+=2;//自加2,因为需要删除S和T
        }
    }
    cout<<S.size()-sumt<<"\n";//最后输出即可
}