学步园

题目链接：http://poj.org/problem?id=1456

//题目大意：
//	有N件商品，分别给出商品的价值和销售的最后期限，只要在最后日期之前销售处，就能得到相应的利润，并且销售该商品需要1天时间。
//问销售的最大利润。
//
//算法分析：
//	贪心。先按时间排序，在按价格进行挑选。
//
//程序代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

#define N 11111

struct Node 
{
	int value,day;
	friend bool operator<(Node a, Node b)
	{
		return a.value > b.value;
	}
};
 
int cmp(Node a, Node b)
{
	return a.day < b.day;
}

int main()
{
	int n;
	Node node[N];
	priority_queue<Node> q;
	while( ~scanf("%d", &n) )
	{
		for(int i = 0; i < n; i++)
			scanf("%d%d",&node[i].value,&node[i].day);
		sort(node, node+n, cmp);		//先按期限天数排序，期限早的排前。
		for(int i = 0; i < n; i++){
			if(node[i].day > q.size())  //如果该商品期限大于队列内已有商品的最大期限（q.size()正好可以看成天数），则入队列。
				q.push(node[i]);
			else if(node[i].value > q.top().value){	//如果商品期限小于已有商品最大期限，但该商品价值却大于已有商品中价值最小的商品，
				q.pop();							//则将已有的价值最小的商品剔除，加入该商品。
				q.push(node[i]);
			}
		}
		int sum = 0;
		while( !q.empty() )		//统计已有商品的总价值。
		{
			sum += q.top().value;
			q.pop();
		}
		printf("%d\n",sum);
	}
}