[构造] UOJ31. [UR #2] 猪猪侠再战括号序列

构造题。要确定目标,考虑目标是弄成 ((((())))) 这样。

从左往右扫,发现右括号,就往右找最近的左括号,翻转这段。

就相当于只交换了一对括号,弱化操作。

这样至多交换 \(n\) 次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int n,m,L[maxn],R[maxn];
char a[maxn];
int main(){
scanf("%s",a+1); n=strlen(a+1)/2;
for(int i=1,p=1;i<=n;i++)
if(a[i]==')'){
if(p<i) p=i; while(a[p]==')') p++;
swap(a[i],a[p]);
L[++m]=i; R[m]=p;
}
printf("%d\n",m);
for(int i=1;i<=m;i++) printf("%d %d\n",L[i],R[i]);
return 0;
}