51Nod

题目链接

题意:给定一个包含“(”,“)”,“?”的字符串,然后现在有一个操作,可以花费ai的价格把“?”转化成“(”,花费bi的价格把“?”转化成“)”。求把该字符串变成合法括号序列的最小费用,若不能输出-1。

思路:记“(”得分为1,“)”,“?”得分为-1,对于一个题目给定的字符串,若得分为负,要做到其能够费用最小且合法,只要找到当前字符串中ai-bi最小的“?”,把其转为“(”即可,得分则+=2,循环该步骤直到其得分>=0为止。

#include<stdio.h>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
#define ll long long
string s;
ll a[50001],r[50001];
priority_queue< ll , vector< ll > , greater <ll> >q;
int main()
{
    cin>>s;
    int m=0;
    for(int i=0;i<s.size();++i)
        if(s[i]=='?')
            ++m;
    ll l;
    for(int i=1;i<=m;++i)
    {
        scanf("%lld%lld",&l,&r[i]);
        a[i]=l-r[i];
    }
    int j=0,sum=0;
    ll ans=0,x;
    for(int i=0;i<s.size();++i)
    {
        if(s[i]=='?')
        {
            ++j;
            q.push(a[j]);
            ans+=r[j];
        }
        if(s[i]=='(')
            ++sum;
        else
            --sum;
        if(sum<0)
        {
            if(q.empty())
                break;
            sum+=2;
            x=q.top();
            ans+=x;
            q.pop();
        }
    }
    if(sum!=0)
        printf("-1\n");
    else
        printf("%lld\n",ans);
}


;