你好，同学。欢迎参加 NOI 专题训练。

今天我们要研究的题目是使括号有效的最少添加。这道题是“合法括号序列”问题的延伸。在竞赛中，括号匹配不仅是栈（Stack）的入门练习，更是贪心策略（Greedy）与线性扫描（Linear Scan）的经典结合。

一、 预备知识点

在挑战本题前，请确保你已经掌握：

1. 合法括号序列的定义：
   • 空字符串是合法的。
   • 如果 A 是合法的，则 (A) 也是合法的。
   • 如果 A 和 B 是合法的，则 AB 也是合法的。
2. 栈（Stack）的思想：利用后进先出（LIFO）处理嵌套关系。
3. 计数器模拟法：对于只有一种括号（如本题只有小括号）的情况，可以用一个整数变量代替栈来维护“当前的平衡度”。

二、 NOI 竞赛题目描述

题目名称：使括号有效的最少添加 (Minimum Add to Make Parentheses Valid) 时间限制：1.0s 内存限制：256MB

【问题描述】 只有当满足下面任一条件时，括号字符串才是有效的：

1. 它是一个空字符串；
2. 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串；
3. 它可以被写作 (S)，其中 S 是有效字符串。

给定一个括号字符串 S，你可以于任何位置插入一个括号（( 或 )）。 例如，如果 S = "())"，你可以插入一个开始括号为 (()))"，或者磁盘插入一个结束括号为 ()())"。 请你返回使结果字符串有效而必须添加的最少括号数。

【输入格式】 输入仅一行，包含一个长度为 $L$ 的字符串 $S$。

【输出格式】 输出一个整数，表示最少需要添加的括号数量。

【样例输入 1】

())

【样例输出 1】

1

【样例输入 2】

(((

【样例输出 2】

3

【数据规模与约定】

• $1 \le L \le 1000$
• S 只包含 '(' 和 ')'。

三、 启发式思路引导：草稿纸上的推演

请拿出草稿纸，我们尝试通过“平衡消除”的方法来思考：

1. 核心矛盾：谁是多余的？

有效的括号序列意味着每一个右括号必须能找到它左边最近的一个左括号与之配对。

• 如果我们遇到一个 )，但左边没有可用的 (，那么这个 ) 就是非法多余的，必须在它前面加一个 (。
• 如果我们扫描完了整个字符串，手里还剩下一堆没被配对的 (，那么这些 ( 也是非法多余的，必须在后面加 )。

2. 草稿纸模拟过程（以 ())(( 为例）

1. 设置两个计数器：need_left（当前急需补左括号的数量），balance（当前手里握着的、还没被抵消的左括号数量）。
2. 开始扫描：
   • 字符 1 (：balance 增加 1。（手里有一个待配对）
   • 字符 2 )：balance 减少 1。（正好配对，手里剩 0 个）
   • 字符 3 )：balance 已经是 0，无法抵消。这个 ) 必须补一个 (。need_left 增加 1。
   • 字符 4 (：balance 增加 1。（手里剩 1 个）
   • 字符 5 (：balance 增加 1。（手里剩 2 个）
3. 结算：
   • 已经确定必补的左括号 need_left = 1。
   • 扫描结束后，手里还剩 balance = 2 个左括号没人要，必须补 2 个右括号。
   • 总和：$1 + 2 = 3$。

四、 算法流程图（伪代码逻辑）

在 C++14 实现中，我们不需要真的开一个栈，只需要维护两个变量。

graph TD
    Start(开始处理字符串) --> Init(初始化 ans 等于 0, balance 等于 0)
    Init --> Loop{遍历字符串每个字符 c}
    Loop -- 遍历结束 --> EndResult(最终答案等于 ans 加 balance)
    
    Loop -- c 是左括号 --> AddBal(balance 增加 1)
    AddBal --> Loop
    
    Loop -- c 是右括号 --> Check{balance 是否大于 0}
    Check -- 是 --> SubBal(balance 减少 1)
    Check -- 否 --> AddAns(ans 增加 1)
    
    SubBal --> Loop
    AddAns --> Loop
    
    EndResult --> Output(输出最终答案)

五、 复杂度分析与优化建议

• 时间复杂度：$O(L)$。
  • 由于我们只需要从左到右扫描一次字符串，且内部操作均为常数级加减法，因此时间复杂度与字符串长度呈线性关系。
• 空间复杂度：$O(1)$ 或 $O(L)$。
  • 如果我们原地读取字符串，仅需两个额外的整数变量，空间复杂度为 $O(1)$。
  • 在竞赛中，存储输入字符串需要 $O(L)$ 空间。

优化建议： 虽然这道题 $L=1000$ 规模很小，但如果遇到 $L=10^6$ 的变体，利用计数器模拟栈的思想将比真的使用 std::stack 对象快得多，因为避免了频繁的动态内存分配和容器开销。

六、 读题关键词总结

在 NOI 竞赛中处理括号类问题，要敏锐捕捉以下词汇：

1. “最少添加” (Minimum Add)：通常暗示了贪心（Greedy）的思想。在括号匹配中，能抵消就抵消是贪心的最优选。
2. “有效” (Valid)：检查是否符合栈的 LIFO 特性。
3. “任何位置插入”：这意味着你不需要考虑具体的插入位置，只需要统计“无法被抵消的孤儿括号”总数即可。

教练寄语： 括号匹配是线性结构中最具美感的问题之一。当你能把一个复杂的栈结构简化为一个简单的计数器（balance）时，你就掌握了数据结构向逻辑转换的精髓。去把代码写出来吧，注意处理好 ans 和 balance 的初始值！