XTU1266:Parentheses（贪心+优先队列）

传送门

题意

从左到右有n个连续的组，每一组有Li个括号，要么全是左括号，要么全是右括号，以及该组的每一个左括号翻成右括号，

或者右括号翻成左括号的花费Di.可以对这n个组的括号进行翻转，每一个括号都可以选择翻或者不翻，使整个括号序列是一个合法括号序列。

分析

首先读入的时候将所有左括号变成右括号，并将费用变成负费用

遍历组，每次计算当前需要多少左括号，条件是如果当前有n个括号，则左括号的个数需>=(n+1)/2。并且将该组括号入优先队列。取优先队列队首进行处理即可

trick

1.XTU的读入读出都要%I64d，就很GG

2.代码一开始很多预处理没写好，要注意

3.大家不妨做做codeforces 3D

代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define F(i,a,b) for(int i=a;i<=b;++i)

#define R(i,a,b) for(int i=a;i<b;++i)

#define mem(a,b) memset(a,b,sizeof(a))

#pragma comment(linker, "/STACK:102400000,102400000")

inline void read(int &x){x=0; char ch=getchar();while(ch<'0') ch=getchar();while(ch>='0'){x=x*10+ch-48; ch=getchar();}}

int n;

struct node

{

    ll num,cost;

    bool operator<(const node &p)const

    {

        return (cost==p.cost)?num<p.num:cost>p.cost;

    }

}a[100100];

ll ans;

ll pre,sum,tmp;

priority_queue<node>q;

char s[10];

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        while(!q.empty()) q.pop();

        ans=pre=sum=0;

        for(int i=1;i<=n;++i)

        {

            scanf("%I64d%s%I64d",&a[i].num,s,&a[i].cost);

            if(s[0]=='(') {ans+=a[i].num*a[i].cost;

            a[i].cost=-a[i].cost;}

        }

        for(int i=1;i<=n;++i)

        {

            sum+=a[i].num;

            tmp=(sum+1)/2-pre;

            pre=(sum+1)/2;

            node tmp1;

            tmp1.cost=a[i].cost;tmp1.num=a[i].num;

            q.push(tmp1);

            //printf("tmp=%lld\n",tmp);

            while(tmp>0&&!q.empty())

            {

                node tmp2=q.top();q.pop();

                //printf("%lld %lld\n",tmp2.num,tmp2.cost);

                if(tmp2.num>tmp)

                {

                    tmp2.num-=tmp;

                    ans+=tmp2.cost*tmp;

                    q.push(tmp2);

                    break;

                }

                else

                {

                    if(tmp2.num==tmp)

                    {

                        ans+=tmp2.cost*tmp;break;

                    }

                    else

                    {

                        tmp-=tmp2.num;

                        ans+=tmp2.cost*tmp2.num;

                    }

                }

            }

        }

        printf("%I64d\n",ans);

    }

    return 0;

}

巴特西

XTU1266:Parentheses（贪心+优先队列）

传送门

题意

分析

trick

代码

最新文章

热门文章