题目描述

难度分:$2600$

输入长度$\leq 5 \times 10^4$的字符串$s$，只包含(，)和?。

设?的个数为$m$，然后输入$m$行，第$i$行两个数$L$和$R$，表示修改$s$中的第$i$个?

为左括号/右括号的花费分别为$L$和$R$，范围$[1,10^6]$。

你需要把$s$中的所有?修改成(或)，使得$s$是一个合法括号字符串。

如果无法做到，输出$-1$。

否则输出最小花费和修改后的字符串。

输入样例

(??)
1 2
2 8

输出样例

4
()()

算法

反悔贪心

遍历$s$串，碰到?就改成右括号，花费加上$R$，维护扫过的区域中，左括号数量减去右括号数量$left$：

1. 如果在某个$s[i]=$?或)的位置$i$（这个位置反正操作完都是)，所以属于同一类）发现前面没有左括号匹配了，即$left=0$，就开始反悔，把前面满足$L-R$最小的?位置改成)。因此，需要一个小根堆来存二元组$(L-R,i)$，便于快速获得这个位置。

2. 如果没有反悔的余地，即反悔堆中没有元素，直接输出$-1$，终止算法。

遍历完数组之后，如果$left=0$，说明整个串左右括号的数量是平衡的，有解，输出最小花费和修改后的$s$串。否则，说明左括号更多，即便是没有出现不能反悔的情况，也是无解的，输出$-1$。

复杂度分析

时间复杂度

遍历字符串$s$的时间复杂度为$O(n)$，在遍历的过程中，对于某个位置$i$，有可能需要对小根堆进行弹出和压入操作，时间复杂度为$O(log_2n)$。因此，整个算法的时间复杂度为$O(nlog_2n)$。

空间复杂度

额外空间就是小根堆的消耗，压到堆中的元素在整个串都是?的情况下达到最大，额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int N = 50010;
int n, l, r;
char s[N];

LL solve() {
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    LL ans = 0;
    int left = 0;
    for(int i = 1; i <= n; i++) {
        if(s[i] == '(') {
            left++;
        }else {
            if(s[i] == '?') {
                scanf("%d%d", &l, &r);
                // 先花费r改成右括号
                s[i] = ')';
                ans += r;
                heap.push({l - r, i});
            }
            if(left > 0) {
                // 右括号有左括号可以匹配
                left--;
            }else {
                // 没有左括号匹配了，要返回之前改的右括号
                if(heap.empty()) {
                    return -1;
                }
                auto pir = heap.top();
                heap.pop();
                ans += pir.first;
                s[pir.second] = '(';
                left++;
            }
        }
    }
    if(left > 0) return -1;
    return ans;
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    int res = solve();
    printf("%lld\n", res);
    if(res != -1) puts(s + 1);
    return 0;
}