描述 Description
Bessie the cow is trying to type a balanced string of parentheses into her new laptop, but she is sufficiently clumsy (due to her large hooves) that she keeps mis-typing characters. Please help her by computing the minimum number of characters in the string that one must reverse (e.g., changing a left parenthesis to a right parenthesis, or vice versa) so that the string would become balanced. There are several ways to define what it means for a string of parentheses to be “balanced”. Perhaps the simplest definition is that there must be the same total number of (’s and )’s, and for any prefix of the string, there must be at least as many (’s as )’s. For example, the following strings are all balanced:
()
(())
()(()())
while these are not:
)(
())(
((())))
给定长度为 n 的一个括号序列，每次修改可以修改一个位置的括号，若这个括号为’(‘，则修改为’)’，若这个括号为’)’，则修改为’(‘，问最少修改多少个使得原括号序列合法。
其中：
① ()是合法的；
② 若 A 是合法的，则 (A) 是合法的；
③ 若 A，B 都是合法的，则 AB 是合法的。
输入格式 InputFormat
一个长度为 n 个括号序列。
输出格式 OutputFormat
最少的修改次数。
样例输入 SampleInput
))()()((())(()))()()
样例输出 SampleOutput
1
代码 Code
考虑每一个右括号必须要有一个在它之前的左括号相配对，所以用 sum 记录到当前位置位置还没有配对的左括号的数量，如果为负数这说明必须有一个右括号要变为左括号，即 ans++ 且 sum+=2（因为少了一个右括号的同时多了一个左括号）。最后加上剩余的未配对的左括号的数量的二分之一即为答案。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
char ch;
int ans,sum;
int main()
{
ch=getchar();
ans=sum=0;
while (ch=='(' || ch==')')
{
if (ch=='(') sum++;
else sum--;
if (sum<0) ans++,sum+=2;
ch=getchar();
}
ans+=sum>>1;
printf("%dn",ans);
return 0;
}