CF1685C. Bring Balance

hfjh · 2023-10-30 22:10:54 · 题解

C. Bring Balance

题意

给你一个括号序列，你可以翻转任意子串，问最少几次反转成合法括号序列。

翻转指 ABC->CBA。

题解

看到括号序列就先想把折线图画出来。

样例 ())((()))(()。

把 ( 看做 +1，) 看做 -1，点坐标就是前缀和。

我们发现操作区间 [l,r] 等同在折线图上把区间 [l,r] 里面的图形按照 l 点和 r 点的中点进行中心对称。

我们发现找出全局最高的点 w，将 [1,w] 和 [w + 1, n] 操作一定会使括号序列合法，所以最多操作两次。

接下来考虑只操作一个区间 [l,r] 的情况。

首先在 y=0 以下的点必须被翻转到，我们找到左边第一个在 y=0 以下的点，l 一定在这个区间内找，r 同理。

在区间内找一个最高的点，这样 l,r 的中点尽可能高，本身在上面的点更不容易翻下去。

然后 check 一下合不合法。

注意特判不需要操作的情况。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
int t, n, a[N], pr[N];
int flag0 = 1, flag1 = 1; 
int l, r, mxl, mxr, wl, wr;
int mx, w;
char x;
void input(){
    cin >> n; n *= 2;
    for(int i = 1; i <= n; ++i){
        cin >> x; 
        if(x == '(') a[i] = 1;
        else a[i] = -1; 
    } 
}
void op(){
    mx = mxl = mxr = -1e9;
    flag0 = flag1 = 1;
    for(int i = 1; i <= n; ++i) pr[i] = pr[i - 1] + a[i]; 
    for(int i = 1; i <= n; ++i) if(pr[i] < 0) flag0 = 0;
    if(flag0){
        cout<<0<<'\n';
        return ;
    }
    for(int i = 0; i <= n; ++i) if(pr[i] < 0) {l = i; break;}
    for(int i = n; i >= 0; --i) if(pr[i] < 0) {r = i; break;}
    for(int i = 0; i <= l; ++i){
        if(mxl < pr[i]){
            mxl = pr[i];
            wl = i;
        }
    }
    for(int i = r; i <= n; ++i){
        if(mxr < pr[i]){
            mxr = pr[i];
            wr = i;
        }
    }
    for(int i = wl; i <= wr; ++i){
        if(mxl + mxr - pr[i] < 0) flag1 = 0;
    }
    if(flag1){
        cout<<1<<'\n';
        cout<<wl + 1<<' '<<wr<<'\n';
        return ;
    }
    for(int i = 1; i <= n; ++i){
        if(mx < pr[i]){
            mx = pr[i];
            w = i;
        }
    }
    cout<<2<<'\n';
    cout<<1<<' '<<w<<'\n';
    cout<<w + 1<<' '<<n<<'\n';
}
int main(){
    cin >> t;
    while(t--){
        input();
        op();
    }

    return 0;
}