Codeforces Beta Round #3 D. Least Cost Bracket Sequence 贪心 优先队列

这题和 Codeforces Round #398 (Div.2) E. Change-free 几乎是同一题啊。

题目传送门

题解传送门

题意：给定一个带有若干问号的左右括号序列，其中第i个问号可以以ai代价改成左括号，也可以以bi代价改成右括号。求一个代价最小的修改问号为左或右括号的方案，输出最终代价以及修改后的合法括号序列。不能修改成合法方案输出-1。

解法：同上面的找钱问题，这题要以满足括号序列合法为前提，使代价最小。首先从左到右扫括号序列：

1.当遇到问号时，若前面左括号数目多于右括号，则暂填右括号，右括号计数+1，并将该位置（反悔能得到的收益，坐标）二元组（bi-ai，i）放进优先队列（最大堆）。因为如果填左括号，可能会因为该位置填了左括号使得原本能够合法的方案变成非法。

2.当遇到问号时，若前面左括号数目等于右括号，则用优先队列在该位置和之前所有填右括号的地方，找一个收益最大的位置进行反悔：右括号改成左括号。左括号计数-1，右括号+1。

3.当遇到左括号时，左括号计数+1。

4.当遇到右括号时，右括号计数+1。此时，若右括号数目多于左括号了：

a.优先队列为空，则无力回天，没有任何可以变回左括号的选择了，输出-1；

b.优先队列非空，用优先队列在已经填好的所有右括号的地方，找一个反悔收益（bi-ai）最大的位置进行反悔：右括号改成左括号。

扫完一遍如果左括号与右括号数目一样，则输出代价和方案数；若不一样，输出-1。

代码如下：

#include <cstdio>#include <cstring>#include <queue>using namespace std;#define fst first#define snd secondtypedef long long ll;typedef pair<ll,int> pli;const int maxn=50005;char s[maxn];int n,m,cnt;ll a[maxn],b[maxn],res;PRiority_queue<pli> que;int main(){    scanf("%s",s);    n=strlen(s);    for (int i=0;i<n;++i)        if (s[i]=='?')            scanf("%lld%lld",&a[i],&b[i]);    for (int i=0;i<n;++i)        if (s[i]=='(')            ++cnt;        else if (s[i]==')') {            --cnt;            if (cnt<0) {                cnt+=2;                if (que.empty()) {                    puts("-1");                    return 0;                }                res-=que.top().fst;                s[que.top().snd]='(';                que.pop();            }        } else {            s[i]=')';            que.push(pli(b[i]-a[i],i));            res+=b[i];            --cnt;            if (cnt<0) {                cnt+=2;                res-=que.top().fst;                s[que.top().snd]='(';                que.pop();            }        }    if (!cnt)        printf("%lld/n%s/n",res,s);    else        puts("-1");    return 0;}