[JSOI2007]建筑抢修

[JSOI2007]建筑抢修
跟经典题poj1456非常像。

首先如果两个都被选入那么截至时间T2小的放前面肯定更优，所以我们先按T2排序。然后逐个遍历建筑，建立一个维修时间为关键字的大根堆，如果前面花费的总时间+维修的时间小于当前的T2，直接加入。否则判断是否小于堆顶，如果小于堆顶则替换，因为是按照T2排序的，所以可以保证能够替换。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define A puts("Yes") 
#define B puts("No")
using namespace std;
typedef long long ll;
const int N=2e5+5;
priority_queue<ll> q;
ll now;
struct node{
	ll t,d;
};
node a[N];
int n;
bool cmp(node a,node b){
	if (a.d!=b.d) return a.d<b.d;
	return a.t<b.t;
}
int main(){
	
//	freopen("data.in","r",stdin);		
	scanf("%d",&n);
	fo(i,1,n) {
		scanf("%lld %lld",&a[i].t, &a[i].d);
	}
	sort(a+1,a+n+1,cmp);
	
	now=0;

	fo(i,1,n) {
		if (now+a[i].t<=a[i].d) {
			now+=a[i].t;
			q.push(a[i].t);
		}
		else{
			if (q.top()>a[i].t){
				now-=q.top();
				q.pop();
				now+=a[i].t;
				q.push(a[i].t);
			}
		}
	}
	printf("%d",int(q.size()));
	return 0;
}