题解：浅嵌套括号的最少反转次数

问题分析

本题要求将一个合法的括号序列通过最少次数的括号反转（开括号变闭括号或反之），使其嵌套深度不超过给定值 ( H )。核心要点包括：

1. 嵌套深度的定义：递归嵌套的最大层数，可通过遍历过程中实时追踪当前深度（开括号+1，闭括号-1）计算。
2. 反转的目的：当当前深度超过 ( H ) 或低于 0 时，通过反转括号调整深度，同时保证最终序列仍合法（题目隐含反转后需合法，而贪心策略可自然满足此条件）。
3. 优化目标：找到最少的反转次数，使整个序列的最大深度不超过 ( H )。

关键思路（贪心算法）

贪心策略的核心的是：在遍历括号序列时，实时调整当前深度，一旦出现深度异常（超过 ( H ) 或小于 0），立即通过反转当前括号修正，确保后续遍历的深度始终在合法范围内。具体逻辑如下：

1. 深度追踪：用变量 now 记录当前嵌套深度，初始为 0。遇到开括号 ( 时 now++，遇到闭括号 ) 时 now--。
2. 异常处理：
   • 若 now > H：当前开括号导致深度超限，反转该开括号为闭括号。此时深度变化为 now -= 2（原本+1，反转后-1，总变化-2），反转次数 ans++。
   • 若 now < 0：当前闭括号导致深度非法（合法序列的深度不会为负），反转该闭括号为开括号。此时深度变化为 now += 2（原本-1，反转后+1，总变化+2），反转次数 ans++。
3. 合法性保证：由于原序列是合法的，且每次反转仅修正当前异常，确保遍历结束后 now 仍为 0（序列合法），同时最大深度不超过 ( H )。

代码解析

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

string s;
int n, m, len, now, ans;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); // 加速输入输出
    cin >> n >> m >> s;
    len = s.size();
    for(int i = 0; i < len; i++){
        if(s[i] == '('){
            now++; // 开括号，深度+1
            if(now > m){ // 深度超限，反转当前开括号
                now -= 2; // 修正深度：+1 变 -1，总变化-2
                ans++; // 反转次数+1
            }
        } else {
            now--; // 闭括号，深度-1
            if(now < 0){ // 深度非法，反转当前闭括号
                now += 2; // 修正深度：-1 变 +1，总变化+2
                ans++; // 反转次数+1
            }
        }
    }
    cout << ans;
    return 0;
}

核心变量说明

• n：括号序列长度（输入参数，实际遍历中用 len 替代，功能一致）。
• m：允许的最大嵌套深度（即题目中的 ( H )）。
• now：当前嵌套深度。
• ans：最少反转次数。

关键步骤解释

1. 输入加速：使用 ios::sync_with_stdio(0) 和 cin.tie(0) 关闭同步流，提升大数据量下的输入效率，适配 ( n \leq 10^6 ) 的数据范围。
2. 遍历处理：逐字符遍历括号序列，根据括号类型更新当前深度，并处理异常情况。
3. 深度修正：通过反转当前括号调整深度，确保深度始终在 [0, m] 范围内，同时累计反转次数。

复杂度分析

• 时间复杂度：( O(n) )。仅需遍历括号序列一次，每个字符的处理为常数时间操作，可高效应对 ( 10^6 ) 级别的输入。
• 空间复杂度：( O(1) )。除存储输入字符串外，仅使用常数个变量，空间开销可忽略。

样例验证

以样例 1 为例：

• 输入：8 2，字符串 (()(()))。
• 遍历过程：
  • 第 0 个 (：now=1（正常）。
  • 第 1 个 (：now=2（正常）。
  • 第 2 个 )：now=1（正常）。
  • 第 3 个 (：now=2（正常）。
  • 第 4 个 (：now=3>2，反转，now=1，ans=1。
  • 第 5 个 )：now=0（正常）。
  • 第 6 个 )：now=-1<0，反转，now=1，ans=2。
  • 第 7 个 )：now=0（正常）。
• 最终输出 2，与样例一致，验证了算法的正确性。

该贪心算法通过局部最优决策实现全局最优解，兼具高效性和简洁性，完美适配题目需求。