小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T部落消灭了所有Z部落的入侵者。但是T部落的基地里已经有 N N 个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序，以抢修尽可能多的建筑。

题解

设修复第 i i 个建筑的时间为 ai a_i ，然后它的 deadline 为 bi b_i 。

一个很显然（但是我没有想到）的贪心思路是对 b b 排序，然后先修理 b b 小的建筑，因为 b b 大的建筑可以拖更长时间，但是 b b 小的建筑 a a 可能很大，这样选择之后或许会导致决策不优。

所以接下来请出正解君 qwq。。

按照上面的思路进行贪心，但是我们维护一个大根堆，堆里维护的是我们要修的建筑的 a a 的值，如果修着修着发现时间不够了，把当前枚举到的建筑的 a a 值和堆顶进行比较，如果当前的 a a 值小于堆顶，就不再修堆顶，改修当前建筑。

这种贪心策略其实就是舍弃耗时大的项目，给后续项目匀时间。

果然团长的贪心还是弱啊。。我好弱啊。。

代码

#include <cstdio>
#include <cstring>
#include <climits>
#include <queue>
#include <algorithm>
const int MAX_N = 150000;
struct Building {
    int a, b;
    bool operator<(const Building &other) const {
        return b < other.b;
    }
} buildings[MAX_N + 1];
std::priority_queue<int> q;
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &buildings[i].a, &buildings[i].b);
    }
    std::sort(buildings + 1, buildings + n + 1);
    int ans = 0, now = 0;
    
    for (int i = 1; i <= n; i++) {
        if (now + buildings[i].a <= buildings[i].b) {
            now += buildings[i].a;
            ans++;
            q.push(buildings[i].a);
        } else {
            if (q.empty()) continue;
            int top = q.top();
            if (top > buildings[i].a) {
                q.pop();
                q.push(buildings[i].a);
                now = now - top + buildings[i].a;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}