题意：给定N个建筑，每个建筑有一个修理时间t1和报废时间t2，每个时刻只能修理一个建筑，求最多可以修理的建筑数
题解：首先将所有建筑按报废时间排序，由小到大枚举，用t1来维护堆，假如已经花费的时间+当前建筑的修理时间<当前建筑的报废时间，当前建筑入堆；否则，假如当前建筑的修理时间比堆顶元素小，并且删除堆顶元素后当前建筑能够维修完毕，那么删除堆顶元素，当前建筑入堆。正确性嘛……对于一个建筑，如果它在a时刻开始修理能修理完毕，那么对于一个b<a，它在b时刻开始修理也必定能修理完，而且相当于在减少了使用时间的情况下修理相同数量的建筑。
#include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <functional> using namespace std; #define ll long long const int MAXN=150000+2; struct Build{ ll t1,t2; friend bool operator<(Build x,Build y){ return x.t2<y.t2;} }b[MAXN],t; int N; ll S; priority_queue<ll> q; int main(){ cin >> N; for(int i=1;i<=N;i++) scanf("%lld %lld",&b[i].t1,&b[i].t2); sort(b+1,b+N+1); for(int i=1;i<=N;i++){ if(S+b[i].t1<=b[i].t2) S+=b[i].t1,q.push(b[i].t1); else if(b[i].t1<q.top() && b[i].t1+S-q.top()<=b[i].t2) S=b[i].t1+S-q.top(),q.pop(),q.push(b[i].t1); } cout << q.size() << endl; return 0; }
原文：http://www.cnblogs.com/WDZRMPCBIT/p/6443429.html
