首页 > 代码库 > codeforces 3D - Least Cost Bracket Sequence(贪心)
codeforces 3D - Least Cost Bracket Sequence(贪心)
题目大意给你一串不确定的括号以及‘?‘,其中‘?‘可以替换成为‘(’与‘)’,并且不同的‘(’需要支付一定的价格,在保证括号合法性的情况下保证最少的价格
分析:
有两个要点:合法性与最少的价格
所以可以在最少价格情况下修正合法性,也可以在保证合法性的情况下修正最小的价格
首先,计算合法性的要点:对于一个括号串,‘(‘即+1,‘)‘即-1,然后把所有的‘?‘都变成‘)‘,如果数值变成负数,则从前面找一个可以使当前括号串价格最小的一个位置变成‘(‘,用优先队列处理。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; #define MAX_NUM 50007 typedef long long LL; char set[MAX_NUM]; LL fir[MAX_NUM]; LL las[MAX_NUM]; struct node{ LL number; LL stp; friend bool operator< (node n1, node n2) { return n1.number < n2.number; } node(LL a,LL b):number(a),stp(b){} }; priority_queue<node> que; int main(int argc, char const *argv[]) { gets(set+1); int strl = strlen(set+1); int cnt = 0; for (int i = 1; i <= strl ; ++i) { if(set[i] == ‘?‘) cnt++; } for (int i = 1; i <= cnt; ++i) { scanf("%lld%lld",&fir[i],&las[i]); } int col = 1; cnt = 0; LL ans = 0; for (int i = 1; i <= strl ; ++i) { if(set[i] == ‘(‘) cnt++; else if(set[i] == ‘)‘) cnt--; else{ cnt--; set[i] = ‘)‘; ans += las[col]; que.push(node(las[col] - fir[col],i)); col++; } if(cnt < 0) { if(que.empty()){ printf("-1\n"); return 0; } node tem = que.top(); que.pop(); ans-=tem.number; set[tem.stp] = ‘(‘; cnt +=2; } } if(cnt==0) printf("%lld\n%s\n",ans,set+1); else printf("-1\n"); return 0; }
codeforces 3D - Least Cost Bracket Sequence(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。