CF1997C Even Positions 题解

题意回顾

有一个长度为 $n$（偶数）的正规括号序列，但所有奇数位置（$1,3,5,\dots,n-1$）的字符丢失了，用 _ 表示。偶数位置的字符已知是 ( 或 )。题目保证至少存在一种把 _ 替换成括号的方法，使整个序列成为合法括号序列（RBS）。

定义括号序列的代价为：所有匹配括号对的下标距离之和。下标从 $1$ 开始。

例如 (())() 的括号对及距离：

• $(1,4)$：$4-1=3$
• $(2,3)$：$3-2=1$
• $(5,6)$：$6-5=1$
  总代价 $=3+1+1=5$。

现在需要在奇数位置填入括号，得到合法括号序列，并使代价最小。输出最小代价。

贪心策略

从左往右扫描序列，维护一个栈 st，存放尚未匹配的左括号的下标。对于每个位置 $i$ 的字符 $c$：

• 若 $c = \texttt{'('}$：确定为左括号，把 $i$ 压栈。
• 若 $c = \texttt{')'}$：确定要与栈顶的左括号匹配，弹出栈顶下标 $p$，答案累加 $i-p$。
• 若 $c = \texttt{'\_'}$（待填位置）：
  • 如果栈非空，就填右括号，与栈顶左括号匹配：答案累加 $i - p$，并弹出栈顶。
  • 如果栈为空，则填左括号，将 $i$ 压栈。

扫描完整个序列后，栈必然为空（保证合法），此时得到的代价就是最小代价。

正确性证明

核心观察：嵌套更深的括号配对会增大距离和。例如 ((())) 的代价是 $5+3+1=9$，而 ()()() 的代价是 $1+1+1=3$。因此，要让总距离尽量小，就应该让每个右括号尽可能早地出现，去匹配最近的左括号。

采用交换论证可以严格证明上述贪心策略的最优性：

假设存在一个最优解 $S_{\text{opt}}$，在某一个 _ 位置，贪心策略选择了填右括号（栈非空），而 $S_{\text{opt}}$ 却填了左括号。那么 $S_{\text{opt}}$ 后续一定会出现一个右括号与这个新左括号匹配，同时原来的栈顶左括号也会在后面某处匹配。通过交换这两次匹配，可以发现总距离不会变大，因此贪心选择不劣。反之，若栈空时贪心填左括号，任何填右括号都会导致序列非法（因为没有可匹配的左括号），所以贪心选择是唯一合法的。

因此，按照“能放右括号就放右括号”的原则能得到最优解。

复杂度分析

只对序列进行一次线性扫描，每个下标最多入栈、出栈各一次，时间复杂度 $O(n)$。对于所有测试用例，$\sum n \le 2\times 10^5$，非常安全。

参考代码

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

signed main()
{
    int _;
    scanf("%lld", &_);
    while (_--)
    {
        int n, res = 0;
        scanf("%lld", &n);
        getchar();          // 读掉换行符
        stack<int> st;
        for (int i = 1; i <= n; i++)
        {
            char c = getchar();
            if (c == '_')
            {
                if (!st.empty())
                {
                    res += i - st.top();   // 填右括号，与最近的左括号匹配
                    st.pop();
                }
                else
                {
                    st.push(i);            // 填左括号
                }
            }
            else if (c == '(')
            {
                st.push(i);
            }
            else // c == ')'
            {
                res += i - st.top();
                st.pop();
            }
        }
        printf("%lld\n", res);
    }
    return 0;
}