题解：CF2196D Double Bracket Sequence

不难发现，在原序列中就已经匹配的直接移除不会使得答案更劣，因为一个括号再花费 $1$ 的代价最多只能与另一个括号匹配。因此，首先对原序列做一次括号匹配，对于同一种类的括号，最终剩下的一定是形如 $\texttt{)) … )(( … (}$ 的。

但是这两种剩余括号是杂糅在一起的，一个最初的想法是不管类型，尝试尽可能的左右括号匹配（花费 $1$ 的代价改变其中的一个括号）。然而很遗憾，这种做法并不正确，反例为 $\texttt{(]](}$。如果尝试先将第 $1$ 个括号和第 $2$ 个括号匹配，最后剩下的两个括号需要再花费 $2$ 的代价。但最优情况下，我们将第 $2$ 个和第 $4$ 个括号翻转，总共只需要花费 $2$ 的代价。

注意到此时已经不存在代价为 $0$ 就能够匹配了，也就是我们想用尽可能多的 $1$ 代价完成剩余的匹配，而只有右括号在左括号前面，类似 $\texttt{)(}$ 的情况需要花费 $2$ 的代价。仔细思考可以发现，需要花费 2 代价的操作不会超过一次。证明如下：

不管类型，若剩余左括号的个数 $x$ 为偶数，则只需要花费 $\frac{x}{2}$ 翻转其中的一半即可匹配所有的左括号。由于 $n$ 是偶数，所以剩余的右括号个数 $y$ 也是偶数，再花费 $\frac{y}{2}$ 即可。
当剩余左括号个数 $x$ 为奇数时，花费 $\lfloor\frac{x}{2}\rfloor$ 可以使得左括号只剩下 $1$ 个，右括号也是如此。通过贪心思想，我们可以留下最左侧的左括号和最右侧的右括号，设下标分别为 $p,q$。则当 $p < q$ 时只需花费 $1$ 的代价，否则需要花费 $2$ 的代价。

因此我们可以得到以下的代码，时间复杂度为 $O(n)$。

void solve ()
{
    int n = read (),ans = 0;
    scanf ("%s",str + 1);
    stack <int> s1,s2;
    vector <int> vis (n + 1);
    for (int i = 1;i <= n;++i)
    {
        if (str[i] == '(') s1.push (i);
        else if (str[i] == '[') s2.push (i);
        else if (str[i] == ')')
        {
            if (!s1.empty ()) s1.pop ();
            else vis[i] = 1;
        }
        else
        {
            if (!s2.empty ()) s2.pop ();
            else vis[i] = 1;
        }
    }
    while (!s1.empty ()) vis[s1.top ()] = 1,s1.pop ();
    while (!s2.empty ()) vis[s2.top ()] = 1,s2.pop ();
    int mn = INF,mx = 0,dx = 0,dy = 0;
    for (int i = 1;i <= n;++i) 
    {
        if (!vis[i]) continue;
        if (str[i] == '(' || str[i] == '[') ++dx,mn = min (mn,i);
        else ++dy,mx = max (mx,i);
    }
    ans += dx / 2 + dy / 2 + dx % 2 + (mn > mx) * (dx % 2);
    printf ("%d\n",ans);
}