Codeforces 26B Regular Bracket Sequence - Solution

1. 题目数据 (Problem Metadata)

• 题目类型：传统题
• 题目链接：Problem - 26B - Codeforces
• 时间限制：5 秒
• 内存限制：256 MB

2. 题意简述 (Problem Summary)

给定长度为 $n$（$1 \le n \le 10^6$）的括号串 $s$，仅由 ( 与 ) 组成。求其最长合法括号子序列的长度。合法括号序列定义为可由 () 经有限次嵌套与拼接得到的序列，空串视为合法。

注意是子序列（可删字符、保相对顺序），不是子串（连续）。

3. 朴素解法 (Brute-Force)

最直接的做法是枚举所有子序列（共 $2^n$ 个），对每个子序列用栈判断是否合法（$O(n)$），总复杂度 $O(n \cdot 2^n)$。$n = 10^6$ 时完全不可行。即便改用区间 DP 求"最长合法子序列"，$O(n^2)$ 在 $n = 10^6$ 下同样超时超内存。

4. 核心解法 (Main Solution)

• 特殊性质：合法括号序列由若干 () 对嵌套/拼接而成，长度必为偶数。子序列允许删除字符，因此只需挑出一组能两两配对的 ( 与 )，且每个 ) 的配对 ( 在它之前即可——所有 ( 在配对意义上是等价的，只有"数量"和"前后位置"起作用。
• 关键突破：一个 ) 能贡献价值，当且仅当它之前存在尚未被匹配的 (。于是采用贪心：从左到右扫描，维护未匹配的 ( 计数 left；遇到 ) 且 left > 0 就配对一次。多余的 ) 直接丢弃（无前置 ( 可配），多余的 ( 在末尾丢弃（无后续 ) 可配）。
• 推导过程：设 res 为成功配对的对数，则 $\text{ans} = 2 \cdot res$

扫描每个字符 $c$：

• $c =$ (：left++
• $c =$ ) 且 left > 0：left--, res++
• $c =$ ) 且 left = 0：跳过

5. 正确性证明 (Proof of Correctness)

方法一：交换论证

设贪心算法匹配对数为 $k$，任意合法子序列的最大匹配对数为 $k^*$。显然贪心解合法，故 $k \le k^*$。下面证明贪心策略不会让结果变得更劣，即证明 $k \ge k^*$

假设存在最优解在某个扫描位置（遇到 ) 且 left>0）选择跳过该右括号，而贪心选择匹配。由于所有左括号在配对中仅提供“一个可用名额”，彼此等价，跳过当前右括号所保留的那个左括号，至多只能与后续某个右括号再配对一次，获得最多 $1$ 对，恰好弥补放弃当前右括号所损失的 $1$ 对，绝不可能带来额外收益。因此将最优解中该处的“跳过”替换为“匹配”，并保持后续配对不变（若这个左括号后续没有被匹配），或将后续匹配前移（相当于去掉了原本匹配这个左括号的右括号），匹配对数必定不会减少，且仍合法。重复替换，可将任意最优解转化为贪心解，故 $k \ge k^*$。综上 $k = k^*$。

直观地，把左括号看作“资源”，右括号看作“机会”。每当有闲置资源时，遇上机会就抓住，肯定不会亏——因为就算这次不用，资源留着以后也只能再换一次机会，最多扯平，不可能赚。所以“能配就配”永远是最优策略。

方法二：上界法

定义前缀差

$$p_i=\#\{(1\le j\le i):s_j=\text{`('}\}-\#\{(1\le j\le i):s_j=\text{`)'}\},\quad p_0=0,$$

令 $m=\min_{0\le i\le n} p_i$，$R$ 为全串右括号总数。

上界：设最长 RBS 的长度为 $L$。任一合法括号子序列中左右括号数相等，长度 $L=2\times \text{（子序列中右括号数）}$。若 $m<0$，则在前缀 $i$ 处右括号比左括号多 $-m$ 个，任何合法子序列在该前缀内必须至少丢弃 $-m$ 个右括号，因此最多保留 $R+m$ 个右括号；若 $m\ge0$，最多保留 $R$ 个。总而言之，有

$$L \le 2\cdot\bigl(R+\min(0,m)\bigr)$$

可达性：贪心算法丢弃右括号的时刻恰是 left=0，即当前前缀差达到新的最小值（为负）。整个过程中丢弃的右括号总数恰好等于 $-\min(0,m)$，故保留的右括号数为 $R+\min(0,m)$。这些保留的右括号都能与之前的左括号配对，构成合法子序列。所以贪心达到上界，必为最优。

直观地，把右括号总数看作“可用需求”。前缀差的最小值 $m$ 刻画了全局资源最紧缺的程度——如果某段前缀右括号过多，那这些多余的右括号无论如何都要被扔掉。贪心算法只在实在没有左括号时才扔右括号，所以它扔掉的正好是必须扔的最少数，剩下的全部都能配成对，自然就是最长。

两种方法总结对比

两种证明殊途同归，均严格证明了贪心算法的正确性。在实际问题中，上界法更易快速建立整体认知，而交换论证更能体现贪心算法的本质思想。

6. 复杂度分析 (Complexity)

• 时间复杂度：$O(n)$，单次线性扫描，$n = 10^6$ 远在时限内。
• 空间复杂度：$O(n)$（存储整个字符串），未超 256 MB；额外工作变量为 $O(1)$。
• 常数优化：可用 getchar 逐字符读入、不存串，将额外空间降至 $O(1)$，但 $O(n)$ 已绰绰有余，不必引入额外编码复杂度。可以参考后面给出的替代版本代码。

7. 实现细节与避坑指南 (Implementation Details)

• 边界条件：
  • 全 ( 或全 )：res = 0，输出 $0$，代码自然处理。
  • $n = 1$：单字符必为 $0$，正确。
  • 形如 )()：第一个 ) 因 left = 0 被跳过，得到 () 长度 $2$，正确。
• 读入：cin >> s 若不加前导空格，则注意索引从 0 开始。

8. 参考代码 (Reference Code)

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

#include <bits/stdc++.h>
using namespace std;
// #define int long long

int calc_RBS(const string &s)
{
    int left = 0, res = 0;
    for (char c : s)
        if (c == '(')
            left++;
        else if (left)
            left--, res++;
    return res * 2;
}

signed main()
{
    ios::sync_with_stdio(false);
#ifdef DEBUG
    clock_t t0 = clock();
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    // Don't stop. Don't hide. Follow the light, and you'll find tomorrow.
    string s;
    cin >> s;
    cout << calc_RBS(s) << endl;

#ifdef DEBUG
    cerr << "Time used:" << clock() - t0 << "ms" << endl;
#endif
    return 0;
}

9. 补充说明 (Additional Notes)

• 经典区分：本题是"最长合法括号子序列"的贪心模型；与之易混的是"最长合法括号子串"（要求连续），后者需用栈或 DP 求解（如 Codeforces 5C Longest Regular Bracket Sequence - Solution / LeetCode 32 / 洛谷 P1944），复杂度同为 $O(n)$ 但思路不同。子序列问题之所以能贪心，正源于"可删字符"带来的自由度——任何 ) 只要前面有富余 ( 就一定值得配对。

替代版本

下面给出逐字符读入、$O(1)$ 额外空间的紧凑写法，避免存储整个字符串，适合 $n$ 极大或对内存敏感的场景。与 §8 主代码复杂度同为 $O(n)$，差异仅在空间常数与是否封装函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int left = 0, res = 0, c;
    while ((c = getchar()) != EOF && c != '\n' && c != '\r')
    {
        if (c == '(') left++;
        else if (c == ')' && left) left--, res++;
    }
    printf("%d\n", res * 2);
    return 0;
}