自动搬运

查看原文

来自洛谷，原作者为

	Albatross_LC 但是有时亦不胜悲伤/于那漫漫长梦中/他创造了没有夏日的世界/在黑日下颤抖着/将自己悲伤的创造视为现实

搬运于2025-08-24 22:51:59，当前版本为作者最后更新于2024-08-05 16:08:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

模拟赛里出了，见有原题，便来水一发题解。

思路：

我们可以把原字符串中的 ( 记为 $1$，将 ) 记为 $-1$，对此序列做前缀和。此时，此题便转换成了另一个问题：

给定一个长度为 $n$ 序列 $a$，每次选择一个数 $i(1\le i\le n)$，将 $a_i$ 到 $a_n$ 都加或减 $1$，使得序列 $a$ 中的数最大值不超过 $L$，最小值不小于 $0$，求最小操作次数

注：此处 $a$ 中最小值不少于 $0$ 是因为在合法的括号序列中，不存在多余的 )，每次匹配的 ( 总在 ) 的左边，所以遍历到 $a_i$ 时，不可能有 $a_i <0$。

此时问题就很简单了，我么只需要对前缀和数组 $a$ 进行一次扫描，记录一个数 $tot$ 为减 $1$ 操作的次数，由于每次修改总会至少改动两个括号，所以当前 $tot$ 的变化量为 $2$，每次对 $a_i - tot$ 判断是否符合要求即可。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int read() {
    int res = 0, c = getchar(), s = 0;
    while (!isdigit(c)) s |= c == '-',c = getchar();
    while (isdigit(c)) res = (res << 1) + (res << 3) + c - '0', c = getchar();
    return s ? -res : res;
}
int n, l, a[N], mx, ans;
char s[N];
int main() {
    n = read(), l = read();
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i ++ )
        a[i] = a[i - 1] + (s[i] == '(' ? 1 : -1), mx = max(mx, a[i]);
    if (mx <= l) cout << 0, exit(0);
    int tot = 0;
    for (int i = 1; i <= n; i ++ )
        if (a[i] - tot > l) {
            ans ++ ;
            tot += 2;
        } else if (a[i] - tot < 0) {
            ans ++ ;
            tot -= 2;
        }
    cout << ans;
}