#5437. 「OOI 2016 Day 2」邪恶联盟 题解

问题分析

我们需要将字符串 $s$ 中的所有 $?$ 替换为 $($ 或 $)$，使得最终字符串的最长合法括号子序列长度最大化。

关键观察：

• 最长合法括号子序列长度 $= 2 \times$ 匹配的括号对数
• 每个匹配的括号对需要一个 $($ 和一个 $)$

贪心策略

核心思想

我们要最大化匹配的括号对数，因此应该：

1. 尽量让 $($ 和 $)$ 数量平衡
2. 保证在任何前缀中，$($ 的数量不少于 $)$ 的数量（用于提取子序列）

具体算法

设：

• $\text{open} =$ 当前可用的 $($ 数量
• $\text{close} =$ 当前可用的 $)$ 数量
• 初始时两个计数器都为 $0$

遍历字符串，对于每个字符：

• 如果是 $($：$\text{open}++$
• 如果是 $)$：$\text{close}++$
• 如果是 $?$：优先设为 $)$（如果 $\text{close} < \text{open}$），否则设为 $($

但这样可能产生无效序列，需要调整。

正确解法

方法：贪心 + 调整

1. 第一次遍历：将所有 $?$ 暂时设为 $)$
2. 检查平衡性：如果出现 $)$ 多于 $($ 的情况，将最右边的某些 $)$ 改为 $($

算法步骤：

• 维护前缀和 $\text{balance}$，遇到 $($ 时 $+1$，遇到 $)$ 时 $-1$
• 当 $\text{balance} < 0$ 时，说明需要将之前的某个 $)$ 改为 $($
• 从右向左调整，选择最右边的 $?$（原本设为 $)$）改为 $($

复杂度分析

• 时间复杂度：$O(|s|)$
• 空间复杂度：$O(|s|)$

实现细节

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.length();
    
    int balance = 0;
    vector<int> question_pos;
    
    // 第一次处理：记录 ? 位置，暂时都设为 )
    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {
            question_pos.push_back(i);
            s[i] = ')';
        }
    }
    
    // 检查平衡性并调整
    int open_count = 0, close_count = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') open_count++;
        else close_count++;
        
        // 如果 ) 太多，需要将之前的某个 ? 从 ) 改为 (
        if (close_count > open_count) {
            if (!question_pos.empty() && question_pos.back() <= i) {
                int pos = question_pos.back();
                question_pos.pop_back();
                s[pos] = '(';
                open_count++;
                close_count--;
            }
        }
    }
    
    cout << s << endl;
    return 0;
}

算法正确性证明

贪心选择性质：

• 将最右边的 $)$ 改为 $($ 可以最大程度地保持后续的平衡性
• 这样调整不会破坏已经形成的合法子序列

最优子结构：

• 每个前缀的最优解包含在全局最优解中
• 通过维护平衡性，我们确保能提取出尽可能多的匹配括号对