程序设计思维与实践 Week10 限时大模拟 A

程序设计思维与实践 Week10 限时大模拟 A"/>

程序设计思维与实践 Week10 限时大模拟 A

题目链接：A-STring

题目描述：
东东有一个字符串X，该串包含偶数个字符，一半是 S 字符，一半是 T 字符
东东可以对该字符串执行 1010000 次操作：如果存在 ST 是该串的子串，则删除掉最左边的 ST。
即 TSTTSS⇒TTSS、SSSTTT⇒SSTT⇒ST⇒空

Input：
字符串X(2 ≦ |X| ≦ 200,000)

Output：
输出最终串的长度

Sample Input：
TSTTSS

Sample Output：
4

思路：
利用栈模拟删除过程，首先S进栈，如果有T，则S出栈，然后减去删除的长度即可。

总结：
使用栈模拟删除其实比较容易方便。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6;
string X;
stack<int> sta;
int child=0;
int main(){cin>>X;int a=X.size();for(int i=0;i<a;i++){if(X[i]=='S')sta.push(1);else{if(!sta.empty()){child+=2;sta.pop();}}}cout<<a-child<<endl;return 0;
}