知识点:
1.关于排列的知识:
一个排列的下一个排列:类似与数字,在最右边加一,然后在变动位置的右边尽量小
上一个:在最右边减一,然后在变动位置的右边尽量大
2.next_permutation,prev_permutation的方法跑得很快,求上一个或者下一个排列的时候可以暴力
3.可以暴力的时候就一定要暴力,暴力安全多了
题目:给定一个括号序列,求比它字典序和刚好大1或小1的合法括号序列
https://nanti.jisuanke.com/t/39615
解法1:
前驱:找一个尽量靠后的位置 ,使得 这个位置上是一个左括号,且 这个位置上 是一个右括号。则前驱中 之前与原串相同, 这个位置是左括号, 这个位置 是右括号, 之后的位置在保证合法的前提下尽量使右括号靠前。 后继:找一个尽量靠后的位置 ,使得 这个位置是一个左括号, 这个位置是一个 右括号,且交换这两个位置得到的括号序列依然合法。则后继中 之前的位置与原串相同, 这个位置是右括号, 这个位置是左括号, 之后的位置在保证合法的前提下 尽量使左括号靠前。
/////////////////////////////////////////Info/////////////////////////////////////////////////
//Problem:
//Date:
//Skill:
//Bug:
/////////////////////////////////////////Definations/////////////////////////////////////////////////
//循环控制
#define CLR(a) memset((a),0,sizeof(a))
#define F(i,a,b) for(int i=a;i<=int(b);++i)
#define F2(i,a,b) for(int i=a;i>=int(b);--i)
#define RE(i,n) for(int i=0;i<int(n);i++)
#define RE2(i,n) for(int i=1;i<=int(n);i++)
//简化敲击
#define PII pair<int,int>
#define PDD pair<double,double>
#define PLL pair<long long ,long long>
#define PB push_back
#define MODY(n) (n%=mod)<0?n+=mod:n
#define MODED(n) ((n)<0?(n)%mod+mod:(n)%mod)
#define x first
#define y second
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const long long llinf = 0x3f3f3f3f3f3f3f3f;
////////////////////////////////////////Options//////////////////////////////////////////////////////
#define stdcpph
#define CPP_IO
#ifdef stdcpph
#include<bits/stdc++.h>
#else
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#ifdef CPP_IO
#include<iostream>
#include<iomanip>
#include<string>
#else
#include<stdio.h>
#endif
#endif
////////////////////////////////////////Basic Functions//////////////////////////////////////////////
template<typename INint> inline void IN(INint &x)
{
x = 0; int f = 1; char c; cin.get(c);
while (c<'0' || c>'9') { if (c == '-')f = -1; cin.get(c); }
while (c >= '0'&&c <= '9') { x = x * 10 + c - '0'; cin.get(c); }
x *= f;
}
template<typename INint> inline void OUT(INint x)
{
if (x > 9)OUT(x / 10); cout.put(x % 10 + '0');
}
////////////////////////////////////////Added Functions//////////////////////////////////////////////
const int maxn = int(1e6+8);
int a[maxn], L[maxn], L1[maxn];
int b[maxn];
int n;
void solve1()
{
memcpy(b,a, sizeof(int)*n);
int p;
F2(i, n - 1, 1)
{
if (a[i]>0 && a[i - 1]<0)
{
b[i - 1] = 1; b[i] = -1; p = i; break;
}
}
int cnt = L1[n - 1] - L1[p];
int cnt2 = (n - 1 - p) - cnt;
int res = cnt2 - cnt; cnt2 = cnt;
F(i, p + 1, n - 1)
{
if (res)
{
--res; b[i] = -1;
}
else if (cnt >= cnt2)
{
--cnt; b[i] = 1;
}
else
{
--cnt2; b[i] = -1;
}
}
F(i, 0, n - 1)cout << (b[i]>0 ? '(' : ')'); cout << '\n';
}
void solve2()
{
memcpy(b, a, sizeof(int)*n);
int p;
F2(i, n - 1, 1)
{
if (a[i]<0 &&a[i-1]>0&& L[i - 1]>=2)
{
swap(b[i], b[i - 1]); p = i; break;
}
}
int cnt = L1[n - 1] - L1[p];
int cnt2 = (n - 1 - p) - cnt;
F(i, p + 1, n - 1)
{
if (cnt-- > 0)b[i] = 1;
else b[i] =-1;
}
F(i, 0, n - 1)cout << (b[i]>0 ? '(' : ')'); cout << '\n';
}
////////////////////////////////////////////Code/////////////////////////////////////////////////////
int main()
{
//freopen("C:\\Users\\VULCAN\\Desktop\\data.in", "r", stdin);
int T(1), cas(0);
#ifdef CPP_IO// CPP_IO
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//cin >> T;
#else
//IN(T);
#endif
/////////////////////////////////////////////////////////////////////////////////////////////////
while (++cas, T--)
{
string s; cin >> s; n = s.size();
F(i, 0, s.size() - 1)
{
a[i] = (s[i] == '('?1:-1);
L[i] = i ? L[i - 1] + a[i] : a[i];
L1[i] = i ? (L1[i - 1] + (a[i] == 1)) : a[i] == 1;
}
solve1();
solve2();
}
///////////////////////////////////////////////////////////////////////////////////////////////////
return 0;
}
//What to Debug
/*
-1.最好把全部warning都X掉,否则:https://vjudge.net/solution/19887176
0.看看自己是否有可能需要快读,禁endl
1.数组越界,爆int,浮点精度(查看精度是否达到题目要求,看有没有浮点数比较:eps),取模操作,初始化数组,边缘数据,输出格式(cas)
2.通读代码,代码无逻辑错误
3.读题,找到题意理解失误或算法错误
4.放弃
*/
解法2:(最优解法)
使用next/prev_permutation直到合法
妈蛋,赛后老实求解拍半天没拍出问题,暴力一分钟解决