题解：CF1821E Rearrange Brackets

DYYqwq · 2026-04-25 10:27:26 · 题解

我们首先注意到每次删去最右侧的括号是最优的。

于是思考如何移动括号。考虑对于一对括号，如果我们选择移动它，那么最贪心的应该是移动到最后面，单独成为一对独立的括号，这样到时候直接删去，不会让别人产生代价。

那么由此，我们计算如果不移动，那么产生的代价是多少。发现只有在这对括号之间的括号会有代价，因为如果它在右括号右边，那么我们会先于这对括号删除它；如果在这对括号左边，那么在删它的时候，这对括号早已经被删除了。

那么代价呼吁而出了，就是这对括号之间的括号对数。因为如果删除中间的一对括号，那么这个右括号就会产生 1 的代价。

我们贪心的选择代价前 k 大的进行移动即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
    int l , r , len;
    bool operator < (const node &qwq) const
    {
        return len > qwq.len;
    }
}a[200010];
bool flag[200010];
void solve()
{
    int k; scanf("%lld" , &k);
    string s; cin >> s;
    stack<int> q; int cnt = 0;
    for(int i = 0 ; i < s.size() ; i ++)
    {
        if(s[i] == '(') q.push(i);
        else
        {
            a[++ cnt] = (node){q.top() , i , i - q.top() + 1};
            q.pop();
        }
    }
    sort(a + 1 , a + cnt + 1);
    for(int i = 1 ; i <= min(k , cnt) ; i ++) flag[a[i].l] = flag[a[i].r] = true;// , printf("%d %d\n" , a[i].l , a[i].r);
    int num = 0 , ans = 0;
    for(int i = s.size() - 1 ; i >= 0 ; i --)
    {
        if(flag[i]) continue;
        if(s[i] == ')') num ++;
        else
        {
            num --;
//          q.pop();
            ans += num;
        }
    }
    printf("%lld\n" , ans);
    for(int i = 1 ; i <= k ; i ++) flag[a[i].l] = flag[a[i].r] = false;
//  for(int i = 0 ; i <= s.size() ; i ++) flag[i] = false;
}
signed main()
{
    int t; scanf("%lld" , &t);
    while(t --) solve();
    return 0;
}