题目大意
给一个序列，序列里面会有左括号、问号、右括号。对于一个?而言，可以将其替换为一个(，也可以替换成一个)，但是都有相应的代价。问：如何替换使得代价最小。前提是替换之后的序列中，括号是匹配的。如果不能替换为一个括号匹配的序列则输出\(-1\)。
输入格式
第一行是序列，序列长度不超过\(5×10^4\)，下面\(m\)(\(m\)是?的数量)行有每行2个数据，第一个是(的代价，第二个是)的代价。
输出格式
第一行打印代价，第二行打印替换后的序列。不行输出\(-1\)。
数据范围
\(1≤a_i，b_i≤10^6\)
样例输入
(??)
1 2
2 8
样例输出
4
()()
思路
使用贪心，首先把所有的?改成)。重新扫描，如果此时右括号的个数比左括号的个数多，那么说明需要修改。此时修改的代价就为\(a[i]-b[i]\)，用小根堆储存，从小的?处开始修改。
无解的情况：
- 最左边是右括号，最右边是左括号。
- 问号的个数比左右括号相差值小。
- 最后匹配完左右括号数不相等。
代码
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
const int maxn=5e4+10;
char s1[maxn],s2[maxn];
ll totl,totr,ans;
ll a[maxn],b[maxn];
priority_queue <pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;int main() {
scanf("%s",s1);
strcpy(s2,s1);
ll len1=strlen(s1),len2=0,sum=0;if(s1[0]==')'||s1[len1-1]=='('){//左边是右括号或者右边是左括号，无解
puts("-1");return 0;
}for(int i=0;i<len1;i++) {
if(s1[i]=='(')totl++;
else if(s1[i]==')')++totr;
else{//否则是问号，先改为右括号
s2[i]=')';
scanf("%d%d",&a[i],&b[i]);
sum++;//问号数+1
}
}if(fabs(totl-totr)>sum){//问号数比左右括号相差数小
puts("-1");return 0;
} totl=totr=0;
if(s1[0]=='?')s2[0]='(';//最左边的肯定改成左括号
totl++;//无论上面那个是否修改s2[0]都肯定是左括号（否则就直接return 0了），先加个1再说
for(int i=1;i<strlen(s2);i++) {
if(s1[i]=='?')q.push(make_pair(a[i]-b[i],i));
if(s2[i]=='(')totl++;
else if(s2[i]==')')totr++;
if(totr>totl){//如果右括号比左括号多，就从小到大改括号方向
s2[q.top().S]='(';
totr--;
totl++;
q.pop();
}
}if(totr-totl){
puts("-1");return 0;
}for(int i=0;i<strlen(s2);i++) {
if(s1[i]=='?'){
if(s2[i]=='(')ans+=a[i];
else ans+=b[i];
}
}cout<<ans<<endl;
cout<<s2;
return 0;
}
