E. Rearrange Brackets 解题思路

核心问题分析

初看这道题，简直是一个嵌套了双层逻辑的“套娃”问题：第一层：给定一个合法的括号序列，每次删去相邻的 () 会产生代价（代价是右侧剩余的括号数）。我们需要找出一个最优的删除顺序，使代价最小。第二层：我们可以进行至多 $k$ 次“大挪移”（抽出任意一个括号插到任意位置），要求移动后的序列依然合法，并且让上述的第一层最小代价进一步达到极小值。

这种题目如果直接去模拟，情况多到爆炸。但只要我们善于做等价转换，就能把它从复杂的字符串操作，降维成最简单的数学贪心。

1. 第一层剥茧：固定序列的最优删除代价

如果序列固定了，怎么删代价最小？题目说：删除相邻 () 的代价是它右边的括号总数。贪心的直觉告诉我们：一定要从右往左删！ 如果我们先删最右边的、最内层的 ()，它右边本来就没有多少括号；如果先删左边的，那右边的一大坨全都会被计入代价。

如果严格从右往左、由内而外地删除，一个 () 被删掉时，它右边到底还剩下哪些括号呢？仔细思考括号的嵌套关系（可以把一对匹配的括号看作树上的一个节点），当一个节点被删时，它右边只剩下包围着它的那些祖先节点的右括号！也就是说，在这个最优删除顺序下，一对括号对总代价的贡献，恰好等于它在括号树中的“深度”（包围它的外层括号对数）。所以，固定序列的最小总代价 = $\sum$ 每对括号的深度。

2. 神奇的树形转换：深度和 = 子树大小和

我们要算所有括号的深度之和，但直接算深度不仅麻烦，而且在移动括号时很难动态维护。这里用到一个极其优美的树形结构性质： 在一棵树（或森林）中，所有节点的“深度之和”，严格等于所有节点的“子树大小之和”！ （因为一个祖先节点会被它的所有子孙节点各算一次深度）。

什么是括号对的“子树大小”？就是被它完全包围在里面的括号对数！ 对于一对匹配的括号，假设左括号位置为 $L$ ，右括号位置为 $R$ 。它们之间包含了多少对括号呢？因为这是一个合法的括号序列，它们中间的字符数一定是偶数，且全都是成对的括号。所以包含的对数就是：

$\text{val} = \frac{R - L - 1}{2}$

顿悟时刻： 这个转化简直是神来之笔！它把一个依赖全局树结构的量（深度），转化成了一个纯局部的量（左右括号的距离）！初始序列的总代价，就是所有匹配括号对的 $\frac{R - L - 1}{2}$ 之和。

3. 第二层剥茧： $k$ 次操作的极致贪心

现在我们要用 $k$ 次操作来减小这个总代价。一次操作是“抽出一个括号插到别的地方”。如果我们把一对距离很远的括号，比如把左括号抽出来，直接插到它的右括号紧前面，那么这对括号就变成了相邻的 ()。它的 $R - L - 1$ 瞬间变成了 $0$ ！它不再包围任何括号了。它释放了里面的所有括号，这就意味着总代价直接减少了这对括号原本的 $\text{val}$ ！

因为我们有 $k$ 次操作机会，想要减去的代价最多，我们只需要：

算出所有括号对的 $\text{val}$ 。
把它们从大到小排序（用优先队列 priority_queue）。
贪心地取出前 $k$ 大的 $\text{val}$ ，从总代价里扣除它们！

代码瞬间变成了找匹配括号 + 排序减法的超级水题。

CPP 代码实现

cpp

// E. Rearrange Brackets

#include <bits/stdc++.h>
#define lg(x) (63 - __builtin_clzll(x))
#define all(x) (x).begin(), (x).end()
#define low_bit(x) ((x) & (-x))
#define pb push_back
#define db long double
#define int long long
#define sz(x) (int)x.size()
#define endl "\n"

using namespace std;

void solve() {

    int k;
    cin >> k;
    string s;
    cin >> s;
    
    // idx 用来给每个左括号分配一个唯一的编号
    int idx = 1;
    stack<int> st;               // 栈，用来进行括号匹配
    priority_queue<int> pq;      // 大根堆，存储每对括号的子树大小（节省代价的潜力）
    
    // l 表示当前字符在一维字符串中的实际位置（1-based）
    int l = 1;
    map<int, int> mp;            // 记录左括号编号 idx 对应的实际位置 L
    int sum = 0;                 // 记录初始的总代价
    
    for (auto it : s) {
        if (it == '(') {
            mp[idx] = l;         // 记录左括号的真实位置
            st.push(idx++);      // 将左括号编号入栈
        } else {
            // 遇到右括号，弹栈匹配
            int temp = st.top(); 
            st.pop();
            
            // 计算当前括号对包围的内层括号对数：(R - L - 1) / 2
            int val = (l - mp[temp] - 1) >> 1;
            
            pq.push(val);        // 将该值丢入大根堆
            sum += val;          // 累加到初始总代价中
        }
        l++;
    }
    
    // 贪心环节：我们可以进行至多 k 次操作
    // 每次操作可以将一对括号压扁，也就是减去它的 val
    int n = sz(pq);
    for (int i = 1; i <= min(k, n); i++) {
        sum -= pq.top();         // 减去当前能省下的最大代价
        pq.pop();
    }
    
    cout << sum << endl;
}

signed main() {
    // 优化输入输出效率
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t; 
    
    while (t--) {
        solve();
    }
}

E. Rearrange Brackets 解题思路 ​

核心问题分析 ​

1. 第一层剥茧：固定序列的最优删除代价 ​

2. 神奇的树形转换：深度和 = 子树大小和 ​

3. 第二层剥茧：kkk 次操作的极致贪心 ​

CPP 代码实现 ​