作为教练，在为 OJ（Online Judge）构造括号类题目数据时，我们需要重点考察平衡度（Balance）的动态变化。

本题的数据生成器不仅要产生随机序列，还要产生**“只有左括号”、“只有右括号”、“完全匹配”以及“大规模嵌套”**等特殊场景。由于 $L=1000$ 规模较小，我们生成的重点在于逻辑覆盖。

一、 数据生成器代码 (C++14)

该程序采用非递归方式逻辑，通过模拟标准算法生成 .out 文件，确保数据的准确性。

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <random>
#include <ctime>
#include <algorithm>

using namespace std;

/**
 * 标程逻辑：用于生成标准输出文件
 */
int get_standard_ans(string s) {
    int res = 0;
    int bal = 0;
    for (char c : s) {
        if (c == '(') {
            bal++;
        } else {
            if (bal > 0) bal--;
            else res++;
        }
    }
    return res + bal;
}

/**
 * 文件写入辅助函数
 */
void write_test_case(int id, string s) {
    string in_file = to_string(id) + ".in";
    string out_file = to_string(id) + ".out";
    
    // 写入输入文件
    ofstream fout(in_file);
    fout << s << endl;
    fout.close();
    
    // 写入输出文件
    ofstream fans(out_file);
    fans << get_standard_ans(s) << endl;
    fans.close();
    
    cout << "Generated Case " << id << " (Length: " << s.length() << ")" << endl;
}

int main() {
    mt19937 rng(time(0));
    
    for (int i = 1; i <= 10; ++i) {
        string s = "";
        
        if (i == 1) { // 样例 1
            s = "())";
        } 
        else if (i == 2) { // 样例 2
            s = "(((";
        }
        else if (i == 3) { // 边界：单个括号
            s = (rng() % 2 == 0) ? "(" : ")";
        }
        else if (i == 4) { // 边界：已经完全匹配的序列
            for(int j=0; j<500; ++j) s += "()";
        }
        else if (i == 5) { // 只有右括号（测试 need_left 累加）
            s = string(1000, ')');
        }
        else if (i == 6) { // 只有左括号（测试 balance 结算）
            s = string(1000, '(');
        }
        else if (i == 7) { // 深度嵌套但合法
            for(int j=0; j<500; ++j) s += "(";
            for(int j=0; j<500; ++j) s += ")";
        }
        else if (i == 8) { // 逆向嵌套（最坏情况：全不匹配）
            for(int j=0; j<500; ++j) s += ")";
            for(int j=0; j<500; ++j) s += "(";
        }
        else if (i == 9) { // 随机中等规模
            int len = 500;
            for(int j=0; j<len; ++j) s += (rng() % 2 == 0) ? "(" : ")";
        }
        else { // 极限规模随机 (L=1000)
            int len = 1000;
            for(int j=0; j<len; ++j) s += (rng() % 2 == 0) ? "(" : ")";
        }
        
        write_test_case(i, s);
    }
    
    return 0;
}

二、 测试点设计说明

作为教练，你需要通过这 10 个测试点覆盖以下思维误区：

三、 考场避坑建议 (针对本题)

1. 关于 ans 的初始值： 在 NOI 考场上，确保你的计数器在处理每个新的测试用例（如果有 T 组数据）前都已经清零。本题虽然只有一组，但这是好习惯。

2. 理解“必须添加”的本质： 告诉学生：“消消乐”思想。

   • 扫描到 ) 时，如果前面有 (，它们两个就“同归于尽”（balance--）。
   • 如果扫描到 ) 前面没东西了，这个 ) 就成了一辈子的“孤儿”，必须给它配一个对（ans++）。
   • 扫描结束后，剩下的所有 ( 也都是“孤儿”，必须给它们配对（ans += balance）。

3. 避免使用 std::stack 对象： 在 $L=1000$ 时使用 std::stack<char> 没问题。但对于 $L=10^6$ 的题目，由于本题只涉及一种括号，计数器（int）的效率远高于容器。在 NOI 这种对常数时间敏感的比赛中，能用 int 就不用 stack。

4. 非递归安全： 数据生成器中，我使用了 string(1000, '(') 等迭代构造方式，完全避开了递归，生成速度极快，且不会产生栈溢出错误。

这份数据生成器产生的 .in 和 .out 文件完全符合 NOI 格式要求。你可以直接编译运行并上传至 OJ 系统。加油！

你好，同学。这道题是括号匹配问题的变体，考查的是对“合法括号序列”平衡条件的深刻理解。在 NOI 竞赛中，虽然我们可以使用栈（Stack）来解决，但由于本题只包含一种括号（小括号），我们可以将空间复杂度优化到极致。

以下是基于 C++14 标准 的竞赛级参考代码。

一、 使括号有效的最少添加 标准题解 (C++14)

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

/**
 * 核心逻辑：
 * 1. 使用 balance 记录当前手里“待匹配”的左括号数量。
 * 2. 使用 need_left 记录因为右括号多余，必须在前面补充的左括号数量。
 * 3. 贪心策略：能抵消就抵消，不能抵消的即为必须添加的部分。
 */

int main() {
    // NOI 竞赛优化：加速 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    if (!(cin >> s)) return 0;

    int balance = 0;    // 当前未被抵消的左括号 '(' 数量
    int need_left = 0;  // 必须在左侧补全的左括号数量

    for (char c : s) {
        if (c == '(') {
            // 遇到左括号，平衡度增加，表示我们需要一个右括号来抵消它
            balance++;
        } else {
            // 遇到右括号
            if (balance > 0) {
                // 如果手里有闲置的左括号，正好抵消
                balance--;
            } else {
                // 易错点：如果手里没有左括号，说明这个右括号是孤立的
                // 我们必须在它左侧某个位置补一个左括号
                need_left++;
            }
        }
    }

    // 扫描结束后：
    // need_left 是因为右括号过剩而必须补的 '(' 数量
    // balance 是扫描完后依然没被抵消的 '(' 数量，必须在右侧补同等数量的 ')'
    int ans = need_left + balance;

    cout << ans << endl;

    return 0;
}

二、 复杂度分析思考过程

1. 时间复杂度分析

• 扫描阶段：程序对输入字符串 S 进行了一次线性遍历。对于每个字符，只进行了常数次加减法判断。
• 结论：时间复杂度为 $O(L)$，其中 $L$ 为字符串长度。对于题目给出的 $L \le 1000$（甚至在更高要求的 $10^6$ 级别），该算法都能瞬间出解。

2. 空间复杂度分析

• 存储开销：我们需要存储输入的字符串。
• 辅助空间：我们只定义了两个整型变量 balance 和 need_left。
• 结论：额外空间复杂度为 $O(1)$。如果不计入存储输入字符串的空间，这是理论上的空间最优解。

三、 关键点与易错点总结

1. 左括号不能抵消它左边的右括号：

   • 例如 ")("。虽然左、右括号各有一个，但它们的顺序不对。
   • 在代码中，当 balance == 0 时遇到 )，必须立即记录 need_left++，因为这个右括号永远无法被它后面的左括号抵消。

2. 结果的组成部分：

   • 很多同学容易漏掉最后剩下的 balance。
   • 记住：合法的括号序列不仅要求在扫描过程中右括号不超标，还要求扫描结束时左括号全部被抵消。

3. 贪心策略的正确性：

   • 为什么“一旦有左括号就抵消右括号”是最优的？因为括号匹配具有“就近原则”，早抵消和晚抵消对最终需要补全的总数没有影响，尽早抵消可以最快地识别出哪些右括号是必须补左括号的。

四、 时间复杂度优化建议

虽然本题的 $O(L)$ 已经非常优秀，但在 NOI 实际竞赛中，如果 $L$ 达到 $10^7$ 甚至更高，可以注意以下几点：

1. 避免频繁的 string 拷贝： 在函数传递参数时，使用 const string& s 而不是 string s，防止大数据量下的内存拷贝开销。
2. 使用 getchar() 或 fread 进行快读： 对于超大规模字符读入，cin 即使加了 sync_with_stdio(false) 依然可能成为瓶颈。使用底层 I/O 可以进一步压低运行时间。
3. 数组模拟： 如果在某些内存极其苛刻的题目中（如只有 1MB 内存），可以边读字符边处理，完全不存储整个字符串，从而将空间复杂度真正降为 $O(1)$。

教练寄语： 这道题是计数器模拟栈的典型应用。当你发现栈中存储的元素只有一种类型且不携带额外信息时，计数器就是最强大的武器。继续保持这种“化繁为简”的思维方式！加油。