UOJ31 【UR #2】猪猪侠再战括号序列题解

题意：

什么魔怔题目（（

有一个由 \(n\) 个左括号 ( 和 \(n\) 个右括号 ) 组成的序列。每次操作时可以选定两个数 \(l, r\)，然后把第 \(l\) 到第 \(r\) 个括号的顺序翻转（括号的朝向保持不变）。例如将 ()((()( 翻转第 \(3\) 到第 \(7\) 个括号后的结果为 ()()(((。

我希望使用不超过 \(n\) 次操作，将这个序列变为一个合法的括号序列。

众所周知，合法括号序列的定义如下：

() 是合法括号序列；

如果 A 是合法括号序列，则 (A) 是合法括号序列；

如果 A,B 是合法括号序列，则 AB 是合法括号序列。

输入格式：

一行一个长度为 \(2n\) 的非空字符串表示初始序列。保证字符串只包含左括号和右括号，且左右括号的个数均为 \(n\)。

输出格式：

对于给出的字符串，输出调整成合法的括号序列的方案。如果不存在这样的方案输出一行一个整数 \(-1\)。

否则，第一行一个整数 \(m\) 表示要进行 \(m\) 次翻转操作。

接下来 \(m\) 行每行两个整数 \(l, r\) 表示要翻转区间 \([l, r]\) 内的括号顺序。翻转操作会按你输出的顺序执行。

请保证 \(m \leq n\) 以及 \(1 \leq l \leq r \leq 2n\)，否则会被判 \(0\) 分。

如果有多组方案，输出任意一组即可。

数据范围：

\(n \le 10^5\)

什么魔怔构造题啊（（

我们直接一个个扫过去，如果是左括号就不管

如果是右括号找到后面第一个左括号，把它们交换就好了

为什么可以直接交换？因为后面第一个左括号前面都是一毛一样的右括号。

然后就好了，没了，就这么水。翻转次数最多 \(n\) 次。

但是还是有一些坑的。

比如数组要开两倍，以及维护的指针 \(j\) 可能会小于 \(i\) （左括号太多导致的），要取个max

时间复杂度 \(O(n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(2e5+15))

char s[N];
int n,cnt,l[N],r[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s+1); n = strlen(s+1) / 2;
    for(int i=1,j=1; i<=n; i++)
        if(s[i] == ')')
        {
            for(j=max(i,j); j <= n * 2 && s[j] == ')'; ++j);
            ++cnt; l[cnt]=i; r[cnt]=j; swap(s[i], s[j]);
        }
    cout << cnt << '\n';
    for(int i=1; i<=cnt; i++)
        cout << l[i] << " " << r[i] << '\n';
    return 0;
}