本文共 1422 字，大约阅读时间需要 4 分钟。

（这个题目看上去没复制完的样子）
还有c++自带的堆…
…
…真香，nb！

题目描述

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

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

输入

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

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

输出

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

若不可能则输出-1。

输入样例

5c 10c 12e 2c 1e 2

输出样例

13

说明

30%的数据满足 N<=20

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

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

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

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

思路

遇到一个事件C，将能涨的钱数加入小根堆中。
如果超出End的范围，便弹出直到小于范围。
这样就可以利用c++自带的小根堆完美地解决此题…
即保证取值合法同时又能取到最大值。

关于堆：

#include<queue>//这是一个小根堆：priority_queue<int,vector<int>,greater<int> > q;//这是一个大根堆：priority_queue<int,vector<int>,less<int> >q;

代码

#include<cstdio>#include<queue>#include<iostream>#include<cmath>#include<algorithm>using namespace std;priority_queue<int,vector<int>,greater<int> > q;int n,s,ans;char c,lc;char readc(){   	c = getchar();	while(c!='c' && c!='e') c = getchar();}int reads(){   	s = 0; lc = getchar();	while(lc>'9'||lc<'0') lc = getchar();	while(lc<='9'&&lc>='0'){   		s = s*10+lc-48;		lc = getchar();	}}int main(){   	scanf("%d",&n);	for(int i = 1; i <= n; ++i){   		readc();		reads();		if(c == 'c')			q.push(s);		else if(i!=n){   			while(q.size()>=s) q.pop();		}	}	while(q.size()){   		ans += q.top();		q.pop();	}	printf("%d",ans);}