[FOJ1903 Regular Brackets]贪心、无权修改括号序列、O(n)

【题目大意】
给定一个括号序列，让你修改最少的次数，使之成为一个合法的括号序列。
输出这个修改次数，并输出最终字典序最小的修改后的结果。
【算法分析】
Orz。。。这类题是我最不擅长的。。。应该说直觉不够好么。。。
下面引用lcc大牛的做法：

先从左向右扫 一旦扫到一个失配的’)’就将左边第一个’）’强转‘（’ 然后反过来做一遍 这样得到的一定是最小转化而且是最小字典序

一开始我也想到个类似的，然后我居然去想，这第一个’)’会不会不能转呢。。。
= =，晕，在正向枚举的时候，stack本来就可以超过0。本就不需要考虑失配。
太SB了。。。然后就这样。
【复杂度】O(n)
【CODE】
#include #include #include const int N=1000005;
int Tc,n,ans;
int Q[N];
char S[N];

void solve1(){
int stack=0,h=1,t=0,i;
for (i=1;i<=n;i++)
if (S[i]=='(‘) stack++;
else{
Q[++t]=i;
if (!stack){
S[Q[h++]]='(‘;
ans++;
stack++;
}
else stack–;
}
}

void solve2(){
int stack=0,h=1,t=0,i;
for (i=n;i>=1;i–)
if (S[i]==’)’) stack++;
else{
Q[++t]=i;
if (!stack){
S[Q[h++]]=’)’;
ans++;
stack++;
}
else stack–;
}
}

int main(){
scanf("%d",&Tc);
for (int i=1;i<=Tc;i++){
scanf("%s",S+1);
n=strlen(S+1);
ans=0;
solve1();
solve2();
printf("Case #%d: %dn",i,ans);
puts(S+1);
}
}