题解：P9805 [POI2022~2023R1] ply

Albatross_LC · 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;
}