【贪心算法】CF3D Least Cost Bracket Sequence

题目大意

洛谷链接
给一个序列，序列里面会有左括号、问号、右括号。对于一个?而言，可以将其替换为一个(，也可以替换成一个)，但是都有相应的代价。问：如何替换使得代价最小。前提是替换之后的序列中，括号是匹配的。如果不能替换为一个括号匹配的序列则输出\(-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;
}