题解 P3056 【[USACO12NOV]笨牛Clumsy Cows】

Berlin_Jacor · 2019-10-06 10:35:20 · 题解

其实这道题并不需要用栈，只要模拟栈的算法原理就可以了，浅显易懂。跑的也不算慢，贴代码：

#include <bits/stdc++.h>
using namespace std;
int ans,sum,i;
string s;
int main(){
    cin>>s;
    int lens=s.size();//这样快 
    for(;i<lens;++i){
        if(s[i]=='(')sum++;//模拟栈 
        else{
            if(sum)--sum;//抵消一个左括号 
            else ++ans,++sum;//变成了左括号 
        }
    }
    ans+=sum>>1;//剩下的都是左括号的情况 ，要有一半变成右括号 
    cout<<ans; 
    return 0;
}