时间限制：0.25s
空间限制：12M
题意
给定一个合法的仅由'(',')'组成的括号序列,求它的下一个合法排列.假定'('<')'.
Solution:
先来回顾求下一个排列的算法:
对于一个排列 1 2 4 5 3
它的下一个排列将从后往前找到相邻的两个数是顺序的(即前面的数小于后面的数),将这两个数交换 得到 1 2 5 4 3
再将后面的所有数反转.
将得到
1 2 5 3 4
即最后结果.
对着道题来说,要保证交换的两个括号后得到的是合法的序列,只要记录每一个'('前面有多少个 '(',记为f[i],')'前面有多少个')',f[j].
由于最后一位一定是')',所以只要在前面找到相邻的两个'('和')' ，（注意到这里也是的顺序）,满足f[i]>f[j];
将最后的‘）’和‘（’ 交换位置，再把后面所以的括号反转。即可得到我们需要的解。
code：
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define sz(x) ((int) (x).size())
const int INF = 11111;
int f[INF], flag;
string s;
int main() {
cin >> s;
int s1 = 0, s2 = 0, len = s.size() - 1;
//记录f数组
for (int i = 0; i <= len; i++) {
if (s[i] == '(') f[i] = s1++;
else f[i] = s2++;
}
for (int i = len, t; i >= 0; i--) {
if (s[i] == ')') t = i;
else if (f[t] < f[i]) {
swap (s[len], s[i]);
//头文<algorithm>里的翻转操作
reverse (s.begin() + i + 1, s.end() );
flag = 1;
break;
}
}
//没有满足条件的顺序括号
if (flag == 0) cout << "No solution";
else cout << s;
}