[BZOJ 1029] [JSOI2007] 建筑抢修 【贪心】

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

const int MaxN = 150000 + 5;

int n, Ans, Time;

struct ES
{
	int Ct, DL;
} E[MaxN];

bool Cmp(ES e1, ES e2) 
{
	return e1.DL < e2.DL;
}

priority_queue<int> Q;

int main() 
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d%d", &E[i].Ct, &E[i].DL);
	sort(E + 1, E + n + 1, Cmp);
	Time = 0; Ans = 0;
	while (!Q.empty()) Q.pop();
	for (int i = 1; i <= n; ++i)
	{
		if (Time + E[i].Ct <= E[i].DL) 
		{
			Time += E[i].Ct;
			Q.push(E[i].Ct);
			++Ans;
		}
		else 
		{
			if (Q.empty()) continue;
			if (E[i].Ct < Q.top()) 
			{
				Time -= Q.top();
				Q.pop();
				Time += E[i].Ct;
				Q.push(E[i].Ct);
			}
		}
	}
	printf("%d\n", Ans);
	return 0;
}