题目

源地址：

http://codeforces.com/contest/3/problem/D

理解

比赛的时候没有做出来，赛后看了琦神的解题报告才明白应该怎么敲。 实际上这个题目需要解决两个问题：第一是合法性，也就是是否满足左右括号匹配；第二是最优化，也就是要求Cost消耗最小。 使用一个变量cnt遍历输入的字符串，遇到'('则自增，遇到')'则自减。这样，只要判断cnt是否为零，就能判断是不是合法。一开始的时候将每一个'?'都重置为')'，然后维护一个保存左右括号消耗差和当前节点的优先队列。然后开始不断地从优先队列中取出键对，使用保存了所有右括号消耗和的ss变量去减。 经过这样的处理之后，cnt只有两种情况。cnt不为零时，说明不可能合法，输出"-1"，cnt为零时，说明有解，输出ss以及最后符合要求的字符串。

代码


#define MAXN 50000+10

char s[MAXN];
ll ss;
int cnt;
int a,b;

priority_queue<pair<ll, int> > que;

int main(int argc, char const *argv[])
{
    scanf("%s", s+1);
    ss=0,cnt=0;
    for(int i=1; s[i]; i++)
    {
        if(s[i]=='(')
        {
            cnt++;
        }
        else if(s[i]==')')
        {
            cnt--;
        }
        else
        {
            scanf("%d%d", &a,&b);
            ss+=b;
            cnt--;
            s[i]=')';
            que.push(pair<ll,int> (b-a,i));
        }
        if(cnt<0)
        {
            if(que.empty()) break;
            pair<ll,int> f = que.top();
            que.pop();
            ss-=f.first;
            cnt+=2;
            s[f.second]='(';
        }
    }
    if(cnt!=0)
        printf("-1\n");
    else
        printf("%lld\n%s\n", ss,s+1);
    return 0;
}

更新日志

  • 2014年11月3日 已AC。