2164.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 2164 on 2006-03-10 at 11:57:40 */ 
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

const int MAX = 800000;

class Order {
public:
	int due, time;
	void make();
	bool operator <(const Order&) const;
};
void Order::make() {
	scanf("%d %d", &time, &due);
}
bool Order::operator <(const Order& o) const {
	return due < o.due;
}

Order order[MAX];

int main()
{
	int i, n;
	
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++) order[i].make();
		sort(order, order+n);
		priority_queue<int> Q;
		int sum = 0;
		for(i = 0; i < n; i++) {
			int k = order[i].time;
			if(sum + k <= order[i].due || (sum != 0 && k < Q.top())) { sum += k; Q.push(k); }
			if(sum > order[i].due) { sum -= Q.top(); Q.pop(); }
		}
		printf("%d\n", Q.size());
	}
	
	return 0;
}