1225.cpp

来自「哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码」· C++ 代码 · 共 43 行

/*  This Code is Submitted by wywcgs for Problem 1225 on 2006-01-10 at 14:27:56 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 10240;

class Good {
public:
	int p, d;
	void make();
	bool operator <(const Good&) const;
};
void Good::make() {
	scanf("%d %d", &p, &d);
}
bool Good::operator <(const Good& g) const {
	return d > g.d;
}

int main()
{
	priority_queue<int> Q;
	Good good[MAX];
	int i, n;

	while(scanf("%d", &n) == 1) {
		good[0].d = good[0].p = 0;
		for(i = 1; i <= n; i++) good[i].make();
		sort(good, good+n+1);
		int profit = 0, t = good[0].d;
		while(!Q.empty()) Q.pop();
		for(i = 0; t > 0; t--) {
			while(i <= n && good[i].d == t) Q.push(good[i++].p);
			if(!Q.empty()) { profit += Q.top(); Q.pop(); }
		}
		printf("%d\n", profit);
	}
	
	return 0;
}