首页 > 代码库 > SGU 179.Brackets light

SGU 179.Brackets light

2024-07-12 09:30:34   222人阅读

时间限制：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;}

　　


联系
我们