哎，昨天一直在赶课设。。没有写
最近听了一些人的建议，停止高级算法的学习，开始刷cf。
目前打算就是白天懒得背电脑的话，系统刷一遍蓝书紫书白书之类的（一直没系统刷过），回宿舍再上机吧。
https://www.luogu.org/problem/CF3D
题意：就是给你一个由 ‘(‘ , ‘)‘ , ‘?‘组成的字符串，可以把‘?‘变成‘(‘或‘)‘，但需要一定的代价，问使得括号匹配前提下的最小代价。
做法：贪心真的是个神奇的东东。。可以这么做，先从左扫到右，遇到‘(‘就mark++，否则mark--（先把问号都当成右括号），如果是问号的话就顺便把它扔到优先队列，优先队列按-b+a排序，然后如果当前mark<0，就弹出个top()，给他变成左括号，优先队列为空说明无解。
#include<cstdio>
#include<queue>
using namespace std;
struct Data { //优先队列的元素
int delta; //这是-b+a
char *p; //这是?的位置
bool operator <(const Data &b)const { //重定义比较运算符进行降序排列
return delta>b.delta;
}
}t;
priority_queue<Data> q; //优先队列
char s[50002];
int main() {
int mark=0; //计数器
long long ans=0;
scanf("%s",s);
for(int i=0,a,b;s[i]&&ans!=-1;++i) {
if(s[i]==‘(‘) //计数器加1
++mark;
else {
--mark; //计数器减1，‘?‘也一样，因为开始时设想所有的‘?‘都是‘)‘
if(s[i]==‘?‘) {
scanf("%d%d",&a,&b);
t.delta=a-b;
t.p=s+i; //给指针赋值
q.push(t); //入队
s[i]=‘)‘;
ans+=b;
}
}
if(mark<0) { //此时要到前面去找‘?‘
if(q.empty())
ans=-1; //如果队列为空，那么字符串不合法
if(ans!=-1) {
mark+=2;
t=q.top(); //取队尾元素并替换
q.pop();
*t.p=‘(‘;
ans+=t.delta;
}
}
}
if(mark) //判断计数器是否为0，否则字符串不合法
ans=-1;
printf("%I64d",ans); //用%I64d
if(ans!=-1)
printf("\n%s",s);
return 0;
}
CF3D Least Cost Bracket Sequence(2500的实力贪心...
原文：https://www.cnblogs.com/wzgg/p/11530964.html