AT_abc428_c 题解

· · 题解

沦落到写 C Sol。

虽然但是对于一个只过了前两题的人来说写 C Sol 不过分对吧。

直接根据栈来判断很麻烦的，因为有删除操作。

但是可以考虑换一个角度，把 ( 看作 1，把 ) 看作 -1，那么判断条件就转化为，所有的加起来为 0，且对于任意前缀都不得为负。

考虑维护前缀 \min，以及其前缀和。这边为了方便直接拿了两个 stack mn 和 sum 来进行维护。

首先考虑加入的操作。很显然的，我们要往 sum 和 mn 里各塞一个东西。sum 里塞的东西很简单，就是这一轮新加的这个字符所对应的数字 x 加上 sum 原本的栈顶的数字即可。而 mn 呢，由于算的是前缀 \min，因此应该是原来的栈顶与 sum 里塞进去的那个数字取 \min 的值。

然后考虑删除的操作。这太不要脑子了！我们直接让 sum 和 mn 分别弹出栈顶即可，因为最后那一位被删掉了，那么它维护的值也就作废了。

int opt=read();
if(opt==1){
    char c;cin>>c;
    int x=(c=='('?1:-1);
    int st=(sum.size()?sum.top():0);
    int mt=(mn.size()?mn.top():0);
    sum.push(st+x);
    mn.push(min(mt,st+x));
}else sum.pop(),mn.pop();

最后那就是判断啦！只有当 sum 的栈顶为 0，且 mn 的栈顶也为 0 的情况下，才是满足条件的哦。当然了，如果两个栈都是空的，那肯定也满足条件啦！

if(sum.empty())cout<<"Yes\n";
else if(!sum.top()&&!mn.top())cout<<"Yes\n";
else cout<<"No\n";

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！