题目大意：
这是一个规则的字符括号序列。一个括号序列是规则的，那么在序列里面插入‘+’ 和 ‘1’ 会得到一个正确的数学表达式。
合法：(())()， ()，(()(()))
不合法：)(，(()，(()))(
给你一个字符序列，里面包含‘（’，‘）’ 和‘？’
我们需要替换所有的‘？’，替换为“（” 和 ‘）’，在所有可能中找到花费最小的。
输入数据：
首先是一个字符串。
然后是m行，每行两个数字ai, 和 bi。
分别代表将第i个问号换为'(' 和‘）’ 的花费。
如果不能得到匹配的串则输出 -1.
==================================================================================================================================================================================
题目解析：
我们遍历串，把所有‘？’变为‘）’, 我们使用一个计数器 cnt, 遇到‘（’ 就 +1， 遇到‘）’ 就 -1.
当我们的cnt为 负数的时候，说明我们必须把前面的一个‘）’变为‘（’才行，这个时候我们需要一个优先队列来存储最优值。其余的自己想想应该就明白了。
#include <iostream> #include <cstdio> #include <cmath> #include <vector> #include <queue> using namespace std; typedef __int64 LL; const LL INF = 1e9+7; const LL MOD = 1e9+7; const LL maxn = 50005; char str[maxn]; LL n; struct node { int a, b, c; int Index; bool friend operator < (node B,node A) { return A.c < B.c; } } P[maxn]; LL solve() { LL k = 0, ans = 0, cnt = 0; priority_queue<node> Q; node Pn; for(int i=0; str[i]; i++) { if(str[i] == '?') { Q.push(P[k]); ans += P[k].b; str[i] = ')'; k ++; cnt --; } else if(str[i] == '(') cnt ++; else cnt --; if(cnt < 0) { while(Q.size() && cnt < 0) { Pn = Q.top(); Q.pop(); cnt += 2; ans = ans - Pn.b + Pn.a; str[Pn.Index] = '('; } } if(cnt < 0) return -1; } if(cnt > 0) return -1; return ans; } int main() { scanf("%s", str); for(int i=0; str[i]; i++) { if(str[i] == '?') { scanf("%d %d", &P[n].a, &P[n].b); P[n].c = P[n].a - P[n].b; P[n ++].Index = i; } } LL ans = solve(); printf("%I64d ", ans); if(ans != -1) puts(str); return 0; }