题目描述

难度分:$2100$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的字符串长度之和$\leq 2 \times 10^5$。

每组数据输入$k(0 \leq n \leq 5)$和一个长度$\leq 2 \times 10^5$的合法括号字符串$s$。

定义$s$的代价为：

• 初始化$cost=0$，不断选取$s$中的一对相邻括号，即$s[i-1]=$(且$s[i]=$)，将这对括号删除，并将$cost$增加$s[i]$右边的括号数量。例如(())删除内层的()会让$cost$增加$1$。

• 如此直到$s$为空。$s$的代价就是最终的$cost$值。

定义$s$的最小代价为：所有删除括号方案的最小代价。

在计算最小代价前，你可以执行如下操作至多$k$次。

• 选择一个$s[i]$，将其移动到 s 的任意位置。需要保证操作后 s 仍然是合法括号字符串。

设操作至多$k$次后得到的字符串为$t$，输出$t$的最小代价的最小值。

输入样例

7
0
()
0
(())
1
(())
5
()
1
(()()(()))
2
((())()(()())((())))
3
((())()(()())((())))

输出样例

0
1
0
0
1
4
2

算法

贪心构造

先考虑某个串$s$的最小代价，肯定是从右往左删除括号能够得到最小的代价，因为这样可以使得每次删除括号时右边的括号数最少，从而每一步的代价最小。而对于其中的某个括号（注意，每次删除的括号必须满足左右括号相邻），如果要将其删除，那么删除它的代价应该是它外面包了几层括号，也就是它自己的深度。因此，整个串$s$的代价就是所有括号的代价之和，可以通过括号匹配的方式计算得到所有括号的深度，将每对括号的代价先累加在$ans$上。

此时$ans$就是$k=0$时的答案，而我们可以进行最多$k$次操作来减小这个$ans$。观察样例可以发现，对于一个括号串A(B)C，要把()删除，可以让)往左跨过B变成A()BC。由于是从右往左删括号：

1. C在最右边，删除C的代价是不变的。
2. 且删完了A的右边才能删A，删除A的代价也不变。
3. 而在A(B)C的状态下，每从B的内部删除一个括号都会加上外层)的代价。但在A()BC模式下B右边没有)，不存在这个代价，因此代价会减少B的括号对数。

这样一来，将所有括号对的代价（任意括号对的代价为这个括号的左右括号距离的一半）存入到一个数组$v$中，然后$ans$减去$v$的$top_k$最大值就是最终的答案。

复杂度分析

时间复杂度

遍历一遍$s$串进行“括号匹配”的时间复杂度为$O(n)$；获得所有括号左右括号的距离数组$v$之后需要将其排序，由于括号的对数为$\frac{n}{2}$，因此时间复杂度为$O(nlog_2n)$（如果用快速选择算法的话时间复杂度可以做到$O(n)$）；最后进行$k$次操作，将代价减小的时间复杂度为$O(k)$。这几步中复杂度最大的就是$O(nlog_2n)$，这也是整个算法的时间复杂度。

空间复杂度

空间瓶颈在于括号匹配时的栈空间和左右括号距离数组$v$，都是线性的，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;
typedef long long LL;

const int N = 200010;
int t, n, k;
char s[N];

void solve() {
    n = strlen(s + 1);
    int dep = 0;
    LL ans = 0;
    vector<int> v;
    stack<int> stk;
    for(int i = 1; i <= n; i++) {
        if(s[i] == '(') {
            dep++;
            stk.push(i);
        }else {
            dep--;
            ans += dep;
            v.push_back((i - stk.top() - 1)>>1);
            stk.pop();
        }
    }
    int sz = v.size();
    sort(v.begin(), v.end());
    for(int i = max(0, sz - k); i < sz; i++) {
        ans -= v[i];
    }
    printf("%lld\n", ans);
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &k);
        scanf("%s", s + 1);
        solve();
    }
    return 0;
}