可以模拟，从后往前找第一个可以变成")"的"("，可以改变的"("要满足他的前面"("个数多于")"的条件。把这个位置改变一下，然后在他之后填充"(……()……)"，这样形成的序列就是所求了。如果找不到可改变的"("，就no solution。
　　Submit 1: RTE on 2。在被改变的位置之后填充的"("的个数计算错了，这会造成WA。程序的结构有所变化。找了一个大数据，居然真挂了：

terminate called after throwing an instance of 'std::length_error'
what(): basic_string::_S_create
忽略 (core dumped)

再次测试，居然不挂了……真诡异。
　　Submit 2: AC。……厄……我做什么了？

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

//AC
#include <iostream>
#include <string>
using namespace std;
 
string seq;
int forw[10000],leftb[10000],rightb[10000];
 
int main()
{
    cin>>seq;
    unsigned i(1);
    for (;i<seq.size();++i)
    {
        forw[i]=(seq[i-1]=='(' ? i-1 : forw[i-1]);
        leftb[i]=leftb[i-1]; rightb[i]=rightb[i-1];
        ++(seq[i-1]=='(' ? leftb[i] : rightb[i]);
    }
    --i;
    while (i)
        if (seq[i]=='(' && leftb[i]>rightb[i])
        {
            int k=seq.size()/2-leftb[i];
            cout<<string(seq,0,i)<<')'<<string(k,'(')<<string(seq.size()/2-rightb[i]-1,')')<<endl;
            return 0;
        }
        else i=forw[i];
    cout<<"No solution"<<endl;
    return 0;
}