首页 > 代码库 > SGU 179.Brackets light
SGU 179.Brackets light
时间限制: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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。