USACO12NOV Clumsy Cows

题目链接

题解

先把能配对的配掉，然后因为剩下的长度一定是偶数，所以可以根据左边)的数目和右边(的数目判断答案。当两者均为偶数时两边各改一半即可，均为奇数则分割处的)(要改成()，之后就转化为偶数的情况。

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
char s[100005];
void init(){
    scanf("%s", s);
}
void solve(){
    int l = 0, r = 0, len = strlen(s);
    for(int i = 0; i < len; ++i){
        if(s[i] == '(') l++;
        else{
            if(l) l--;
            else r++;
        }
    }
    printf("%d\n", ((l + 1) >> 1) + ((r + 1) >> 1));
}
int main(){
    init();
    solve();
    return 0;
}