题面：均匀的括号（Bracket.cpp）

题目描述

​ 我们按如下方式递归定义一个合法的括号序列及其深度：

  1. 空串是一个合法的括号序列，且深度为 $0$ 。
  2. 若 $S$ 是一个合法的括号序列且深度为 $h$ ，则 $(S)$ 是一个合法的括号序列且深度为 $h+1$ 。
  3. 若 $A,B$ 都是合法的括号序列，且深度分别为 $h_A,h_B$ ，则 $A+B$（其中 + 表示字符串的拼接）是一个合法的括号序列且深度为 $max(h_A,h_B)$ 。

​ 若一个括号序列是合法的且深度 $≤L$ ，则称其是一个均匀的括号序列。现在给你一个合法的括号序列 $S$ 及正整数 $L$ ，问要使其均匀，至少要修改其中多少个括号。（容易发现，当 $L$ 是正整数时，至少存在一种方案)

思路：暴力 & 正解（贪心）

暴力很简单，直接暴力枚举所有状态，然后把合法的串给和原串匹配，取最小值。

1
2
3
4
5
6
7
def main() :
	GetSbit()                                // 获得 S 对应二进制
    ans = inf
    for i 0 -> Pow(2, n) - 1                 // 暴力枚举所有状态
    	if Check(i)                          // 判断是否合法
        	ans = min(ans, Diff(Sbit,  i))   // 寻找不同之处的个数
    print(ans);                              // 打印答案

接下来我们想正解。最直观的想法，就是遇到一个非法的括号就拆，但是这样显而易见是不优的。考虑优化。
我们发现，对于一对非法的括号（深度非法，因为题目保证给出的是合法括号序列）拆除是解决的最好方式。而我们要考虑的是，拆除的位置是否有影响。假设非法括号对的下表是 $x$ ，那么 $x$ 以前一定都是合法，不然会优先拆除前面，而后面的不管是拆在 $x$ 点还是 $x$ 点以前，都是一样的。所以直接开贪。

代码：正解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

int n, L;
char s[N];
void flip(int pos) {
    s[pos] = (s[pos] == '(') ? ')' : '(';
}
int sum;
int ans;

void Input() {
    scanf("%d%d", &n, &L);
    scanf("%s", s + 1);
}

void Work() {
    for (int i = 1; i <= n; i++) {
        if (s[i] == '(' && sum == L) {
            flip(i), ans++;
        }
        if (s[i] == '(') sum++;
        else sum--;
        while (sum < 0) ans++, sum += 2;
    }
    printf("%d", ans);
}

int main() {
    Input();
    Work();
    return 0;
}