CF3D

__S08577__ · 2025-08-25 10:31:24 · 题解

题意

题目传送门

思路

不妨把 ? 全部换成)，用优先队列（小根堆）记录每一个问号将)变成(的代价，如果不合法，就弹出堆首，并将)改成(即可

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<set>

using namespace std;

#define int long long
#define ll long long
#define Endl cout<<endl;
#define ENdl Endl
#define xy cout<<"xy";
#define yx cout<<"yx";
#define pii pair<int,int>
#define lowbit(x) x&(-x)
#define fi first
#define se second
#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int N=2e5+10;//注意修改
const int mod=1e9+7;
const int Max=0x3f3f3f3f3f;

string s;
int t=0;
priority_queue<pii,vector<pii>,greater<pii> > q;
/*
 */
signed main(){

//   freopen("a.in","r",stdin);
//   freopen("a.out","w",stdout);

    cin>>s;
    int res=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='(') t++;
        else if(s[i]==')'){
            t--;
        }else{
            int x,y;
            cin>>x>>y;
            q.push(make_pair(x-y,i));
            t--;
            res+=y;
            s[i]=')';
        }
        if(t<0){
            if(q.empty()){
                cout<<-1;
                return 0;
            }
            pii p=q.top();
            q.pop();
            s[p.se]='(';
            t+=2;
            res+=p.fi;
        }
    }
    if(t) {
        cout<<-1;
        return 0;
    }
    cout<<res<<endl;
    cout<<s;
    return 0;
}

/*
 1
 5 3
 2 4 5

 */