I 贪心 + 细节

题意

给你一个串，其中 * 代表可以填充的地方。题目要求你填充 * 部分，使得这个串“括号匹配”，并且填充次数最小，其括号部分字典序最小。

思路

一开始就想到贪心，但是细节想了很久。

其实最关键是发现一个性质，如果在子串 $s[1:i]$，左右括号数目不等。

  1. 左括号有不匹配：找到离它右侧最远的 *, 替换成右括号即可
  2. 右括号有不匹配：找到离它左侧最远的 *, 替换成左括号即可
  3. 如果上面任一环节找不到对应的 *, 必然匹配失败

而且这个方法恰好能使填充次数最小，并且保证字典序最小。

写一个双端队列，扫描过程中同时维护队列中 * 的位置即可。

代码

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

const int N = 1e5 + 5;
int Star[N], Left[N];
char s[N];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%s", s);

        int success = true, tot = 0;
        int starFront = 0, starTail = 0;
        int leftTop = 0;

        for (int i = 0; s[i] && success; ++i) {
            if (s[i] == '*') {
                Star[starTail++] = i;
            } else if (s[i] == '(') {
                Left[leftTop++] = i;
            } else {
                if (leftTop) {
                    --leftTop;
                } else if (starTail - starFront) {
                    s[Star[starFront++]] = '(';
                } else {
                    success = false;
                }
            }
        }

        while (leftTop && success) {
            if (starTail - starFront && Star[starTail - 1] > Left[leftTop - 1]) {
                s[Star[--starTail]] = ')', --leftTop;
            } else {
                success = false;
            }
        }

        if (!success) {
            puts("No solution!");
        } else {
            for (int i = 0; s[i]; ++i)
                if (s[i] != '*') s[tot++] = s[i];
            s[tot++] = 0;
            puts(s);
        }
    }
    return 0;
}