CF3D Least Cost Bracket Sequence

题目：

给定一个序列，序列中有左括号、问号、右括号。对于一个？，可以替换成(花费为ai，可以替换成’)'花费为bi。问是否可以在代价最小的情况下，将原序列变成一个合法的括号序列。
如果可以，请输出花费，以及括号序列是怎样的
否则输出-1

解决：

首先，我们可以将问号全部变成)，同时记录已有的花费，然后用cnt记录未匹配的(的个数，如果小于0了，说明对于当前’)‘多，为了合法，我们必须将某一个？有’('变成(，贪心的考虑，找到bi-ai最大的那个找出来，然后减去最优。
这一操作可以利用大根堆解决

代码：

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
typedef long long ll;
const int N = 50010;
char s[N];
int a[N], b[N];
priority_queue<PII> q;
int main()
{
    cin >> s + 1;for (int i = 1; s[i]; i ++ )if (s[i] == '?') scanf("%d%d", &a[i], &b[i]);ll sum = 0;int cnt = 0;for (int i = 1; s[i]; i ++ ){
    if (s[i] == '(') cnt ++;else if (s[i] == ')') cnt --;else{
    cnt --;s[i] = ')';sum += b[i];q.push({
    b[i] - a[i], i});}if (cnt < 0){
    if (q.empty()) break;cnt += 2;PII t = q.top();q.pop();sum -= t.first;s[t.second] = '(';}}// cout << cnt << endl;if (cnt != 0){
    cout << "-1" << endl;}else{
    cout << sum << endl;cout << s + 1 << endl;}return 0;
}