Description
小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的
入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全
毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需
要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一
段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多
的建筑。
Input
第一行是一个整数N接下来N行每行两个整数T1,T2描述一个建筑：修理这个建筑需要T1秒，如果在T2秒之内还
没有修理完成，这个建筑就报废了。
Output
输出一个整数S，表示最多可以抢修S个建筑.N < 150,000; T1 < T2 < maxlongint
Sample Input
4
100 200
200 1300
1000 1250
2000 3200
100 200
200 1300
1000 1250
2000 3200
Sample Output
3
贪心
先按照deadline进行排序，优先处理deadline小的建筑，记录当前已经花费的时间cost，pq记录最大的时间
如果cost <= deadline 直接将当前时间push入堆
如果cost > deadline 考虑将花费时间最大的弹出，查看弹出后是否能修理当前建筑以及时间是否能变小，能变小则弹出并将当前的花费push入堆
1 // luogu-judger-enable-o2 2 #include <bits/stdc++.h> 3 using namespace std; 4 #define lop(i,a,b) for(register int i = (a); i <= (b); ++i) 5 inline int read(){ 6 ???????register int c = getchar(), x = 0, f = 1; 7 ???????while(!isdigit(c)){if (c == ‘-‘) f = -1; c = getchar();} 8 ???????while(isdigit(c)) x = (x<<3)+(x<<1)+(c^48), c = getchar(); 9 ???????return x * f;10 }11 const int N = 150005;12 int n;13 priority_queue <int> q;14 int dead, cost, cnt;15 struct build{16 ????int t1, t2;17 ????inline bool operator < (const build &rhs) const {18 ????????return t2 < rhs.t2;19 ????}20 }b[N];21 int main(void){22 ????n = read();23 ????lop(i,1,n) b[i].t1 = read(), b[i].t2 = read();24 ????sort(b+1, b+1+n);25 ????lop(i,1,n) {26 ????????cost += b[i].t1, dead = b[i].t2;27 ????????if (cost <= dead) q.push(b[i].t1);28 ????????else {//cost > dead29 ????????????int x = q.top();30 ????????????if (cost - x <= dead && x > b[i].t1) {31 ????????????????q.pop();32 ????????????????q.push(b[i].t1);33 ????????????????cost -= x;34 ????????????}35 ????????????else cost -= b[i].t1;36 ????????}37 ????}38 ????cout << q.size();39 ????return 0;40 }[BZOJ1029][P4053][JSOI2007]建筑抢修 ?(贪心+堆)
原文地址：https://www.cnblogs.com/Ycrpro/p/8456881.html