题解 P3056 【[USACO12NOV]笨牛Clumsy Cows】
ljc20020730
2019-08-06 21:20:54
好久没刷水题了，水一篇博客。
看到题解区那么鱼龙混杂的题解，我还是先抛砖引玉，讲一个最简单的也最容易理解的题解吧。
首先，我们贪心的想将足够多的()括号匹配掉。这可可以使用栈来实现，如何当前元素为(那么直接插入栈，如果为)那么如果栈顶元素为(那么弹栈找到一组合法匹配，否则插入栈顶。
最终栈中元素必然是$cnt1$个`(`和$cnt2$个`)`组成的，所以将两个(部分和)部分分开考虑，在每一个相同符号的区域内，先间隔地把符号取反，然后最终可能会剩余一个`)(`然后再加`2`即可。
综上所述，如果$cnt_1 $和$cnt_2$的都是偶数直接输出$(cnt_1 + cnt_2)/2$否则输出$(cnt_1 + cnt_2)/2 + 2$
你懂了么。
```cpp
# include<bits/stdc++.h>
using namespace std;
stack<char>t;
char s[100010];
int main()
{
scanf("%s",s+1); int len=strlen(s+1);
for (int i=1;i<=len;i++) {
if (s[i]=='(') t.push('(');
else {
if (t.size()&&t.top()=='(') t.pop();
else t.push(')');
}
}
int cnt1=0,cnt2=0;
while (t.size()) {
if (t.top()==')') cnt1++;
else cnt2++;
t.pop();
}
if (cnt1%2==0&&cnt2%2==0) printf("%d\n",(cnt1>>1)+(cnt2>>1));
else printf("%d\n",(cnt1>>1)+(cnt2>>1)+2);
return 0;
}
```