原题链接
题目描述：小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一 段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多 的建筑。
输入格式：第一行是一个整数N接下来N行每行两个整数T1,T2描述一个建筑：修理这个建筑需要T1秒，如果在T2秒之内还没有修理完成，这个建筑就报废了。
输出格式：输出一个整数S，表示最多可以抢修S个建筑.N < 150,000; T1 < T2 < maxlongint
输入样例： 4 100 200 200 1300 1000 1250 2000 3200
输出样例： 3
解析：第一眼看上去完全没有思路，感觉是贪心却不知道怎么贪。 想了一会注意到每个建筑对答案的贡献都是1，不管取哪几个对答案都不会产生影响。 所以可以先按照T2从小到大排序，进行贪心。 如果发现无法按时完成，就从优先队列中找出之前修过的建筑中所需时间最长的进行替换。 显然，这样可以保证完成相同的修建数而时间最小。
代码如下：
#include<cstdio> #include<algorithm> #include<queue> using namespace std; const int maxn = 150005; int n, ans, tim; struct node{ int x, y; }a[maxn]; priority_queue <int> heap; int read(void) { char c; while (c = getchar(), c < '0' || c >'9'); int x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; } int cmp(node a, node b) { return a.y < b.y; } int main() { n = read(); for (int i = 1; i <= n; ++ i) a[i].x = read(), a[i].y = read(); sort(a + 1, a + 1 + n, cmp); heap.push(0); for (int i = 1; i <= n; ++ i) { if (tim + a[i].x > a[i].y) { int tmp = heap.top(); if (tmp > a[i].x) heap.pop(), heap.push(a[i].x), tim -= tmp - a[i].x; } else heap.push(a[i].x), ans ++, tim += a[i].x; } printf("%d", ans); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10206011.html
相关资源：JAVA上百实例源码以及开源项目