JZOJ 3487. 【NOIP2013模拟联考11】剑与魔法(dragons)

3487. 【NOIP2013模拟 联考11】剑与魔法(dragons) (Standard IO)

Time Limits: 1000 ms Memory Limits: 131072 KB Detailed Limits

Goto ProblemSet

Description

万老师听说某大国很流行穿越，于是他就想写一个关于穿越的剧本。

闲话休提。话说老师穿越到了某一个剑与魔法的大陆。因为如此这般，所以老师从维娜艾那里得到了预言。老师一共被告知了若干件按顺序结算的事件。这些事件分为两类：战役事件（CASE）、穿越回去事件（END）。战役事件可以选择是否参加，参加了之后会获得一定的金钱。每个END事件发生需要至少参加一定数量的战役事件。特别的是，END事件如果满足要求就会强制发生。老师希望在大陆玩个够，所以他要求只有最后一个END事件会发生。老师希望获得最多的金钱，所以求助于你。

Input

第一行一个数N，表示输入文件有多少行。

接下来每一行用空格隔开一个字符和一个整数。字符为“c”表示战役事件，接下来的整数表示这次涨RP顺带有多少钱；字符为“e”表示穿越回去事件，接下来的整数代表至少要涨多少RP。最后一个事件保证是END事件。

Output

第一行一个整数，最多金钱数目。

若不可能则输出-1。

Sample Input

Sample Output

Data Constraint

30%的数据满足 N<=20

60%的数据满足 N<=1,000

100%的数据满足 N<=200,000

每次涨RP事件赏金不超过10,000

穿越事件的要求不超过200,000

做法：打一个优先队列实时维护即可

#include <cstdio>

#include <cstring>

#include <iostream>

#include <queue>

using namespace std;

priority_queue<int> q;

int n;

char c;

long long ans;

int main()

{

    scanf("%d", &n);

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

    {

        int x = ;

        cin >> c;

        if (c == 'c')

        {

            scanf("%d", &x);

            x = -x;

            q.push(x);

        }

        else

        {

            scanf("%d", &x);

            while (q.size() >= x && i != n)    q.pop();

        }

    }

    while (!q.empty())

    {

        int x = q.top();

        x = -x;

        ans += x;

        q.pop();

    }

    printf("%d", ans);

}