[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;
}