当前位置:首页 > 数据结构 > XTU 1266 Parentheses

XTU 1266 Parentheses

Parentheses

Bobo has a very long sequence divided into n consecutive groups. The i-th group consists of li copies of character ci where ci is either "(" or ")".

As the sequence may not be valid parentheses sequence, Bobo can change a character in the i-th group from "(" to ")" (and vice versa) with cost di. He would like to know the minimum cost to transform the sequence into a valid one.

Note:

  • An empty string is valid.

  • If 

    S

     is valid, 

    (S)

     is valid.

  • If 

    U,V

     are valid, 

    UV

     is valid.

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains an integer n. The i-th of the following n lines contains li,ci,di.

  • 1n105
  • 1l1+l2++ln109
  • l1+l2++ln

     is even.

  • 1di109
  • The sum of 

    n

     does not exceed 

    106

    .

Output

For each case, output an integer which denotes the result.

Sample Input

4
1 ( 1
1 ( 2
1 ( 3
1 ) 4
2
500000000 ) 1000000000
500000000 ( 1000000000

Sample Output

2
500000000000000000

Note

For the first sample, Bobo should change only the character in the second group.

For the second sample, Bobo should change half of characters in both groups.


输入n  然后是n组括号  比如第二个用例 500000000 ( 1000000000 就是连续有500000...个左括号 把其中任意一个转成右括号 需要花费1000..... 问组成最合理的括号串 需要的最少花费

对于第二组样例  把第一组括号前一半换成左括号  第二组的后一半换成右括号  每一次花费的是一样的  这是碰巧的 250000000*1000000000 再*2 所以得到答案


思路

 

把(变成)花费由正变成负 然后用个堆来维护(保存可以翻过去变成左括号的括号群)  在这里如果不合理那我就从堆中取出在此之前的右括号(而且这个右括号翻过来是在现在这个点之前来说最划算的)就这样贪心跑过去 

又是卡时间过的- -  2600+ms

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <cmath>
using namespace std;

#define ll __int64
#define N 100005
struct p
{
    ll l,d;
    char c;
    bool operator < (const p&r)const
    {
        return d>r.d;
    }
} a[N];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        priority_queue<p>q;
        ll ans=0;
        for(int i=1; i<=n; i++)
        {
            scanf("%I64d %c %I64d",&a[i].l,&a[i].c,&a[i].d);
            if(a[i].c=='(')
            {
                ans+=a[i].l*a[i].d;
                a[i].d=-a[i].d;
            }
        }
        ll len=0;///已经确定了多少个左括号
        ll sum=0;///总长
        ll temp;///temp为需要的左括号
        for(int i=1; i<=n; i++)
        {
            sum+=a[i].l;
            q.push(p {a[i].l,a[i].d});
            ll temp=(sum+1)/2;
            if(len<temp)
            {
                temp=temp-len;
                while(!q.empty())
                {
                    p t=q.top();
                    q.pop();
                    if(t.l>=temp)
                    {
                        ans+=temp*t.d;
                        t.l-=temp;
                        len+=temp;
                        temp=0;
                        if(t.l!=0)
                            q.push(p {t.l,t.d});
                        break;
                    }
                    else
                    {
                        len+=t.l;
                        temp-=t.l;
                        ans+=t.l*t.d;
                    }
                }
                if(temp>0)
                {
                    ans+=(temp+1)/2*a[i].d;
                    if(temp/2)
                    q.push(p{temp/2,a[i].d});
                }
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}


除特别注明外,本站所有文章均为whppmy原创,转载请注明出处来自http://www.dengwenhuo.cn/?id=455

发表评论

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。