codeforces 3D Least Cost Bracket Sequence

贪心， 从左到右扫描，每个问号默认都变成右括号，如果左括号不够，那么就用前面的右括号去换左括号代价是-b+a，找代价最小的（set或者堆维护）。

#include<bits/stdc++.h>
using namespace std;
int const N=50000+10;  
char s[N]; 
struct node{
	int p,v; 
	bool operator < (const node &rhs) const{
		if(v!=rhs.v) return v<rhs.v; 
		else return p<rhs.p;  
	}  
};  
set<node> se;  
int vis[N],a[N],b[N];  
int main(){
	scanf("%s",s);  
	int n=strlen(s); 
	int m=0,num=0;  
	long long ans=0;  
	for(int i=0;i<n;i++){ 
		if(s[i]==‘(‘) num++; 
		else if(s[i]==‘)‘){
			if(num==0){  
				if(se.size()==0) {
					cout<<-1<<endl;  
					return 0;  
				}  
				node t=*se.begin();  
				vis[t.p]=1;  
				ans+=t.v;   
				se.erase(t);   
				num++; 
			}else num--;  
		} else {
			m++;scanf("%d%d",&a[m],&b[m]);   
			ans+=b[m];  
			if(num) {
				num--;  
				node t;  
				t.p=i;  
				t.v=-b[m]+a[m];  
				se.insert(t);  
			}  
			else {
				node t;  
				t.p=i; t.v=-b[m]+a[m];   
				se.insert(t);  
				t=*se.begin();  
				ans+=t.v;  
				vis[t.p]=1;   
				se.erase(t);  
				num++;  
			}   
		}  
	}   
	if(num){
		cout<<-1<<endl;  
		return 0;  
	}  
	printf("%lld\n",ans);    
	for(int i=0;i<n;i++)  
		if(s[i]!=‘?‘) printf("%c",s[i]);  
		else if(vis[i]) printf("(");  
		else printf(")");  
	printf("\n");  
	return 0; 
}  

codeforces 3D Least Cost Bracket Sequence

原文：https://www.cnblogs.com/ZJXXCN/p/14803829.html