首页 > 代码库 > bzoj3016[Usaco2012 Nov]Clumsy Cows*

bzoj3016[Usaco2012 Nov]Clumsy Cows*

bzoj3016[Usaco2012 Nov]Clumsy Cows

题意:

给定长度为n的一个括号序列,每次修改可以修改一个位置的括号,若这个括号为’(‘,则修改为’)’,若这个括号为’)’,则修改为’(‘,问最少修改多少个使得原括号序列合法。
其中:()是合法的;若A是合法的,则(A)是合法的;若AB都是合法的,则AB是合法的。n≤100000。
题解:
思路很简单,然而我没法知道它的正确性:对序列扫一遍,如果遇到右括号且当前右括号个数大于左括号个数,则将该右括号改为左括号。扫完之后统计若左括号多则往后将一半的左括号改为右括号。
代码:
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define inc(i,j,k) for(int i=j;i<=k;i++)
 5 using namespace std;
 6 
 7 char ch; int s,ans;
 8 int main(){
 9     ch=getchar();
10     while(ch!=\n){
11         if(ch==()s++; if(ch==)){s--; if(s<0)s+=2,ans++;} ch=getchar();
12     }
13     ans+=s/2; printf("%d",ans); return 0;
14 }

 

20161019

bzoj3016[Usaco2012 Nov]Clumsy Cows*