题解 | [JSOI2007]建筑抢修

// 构造优先队列，超时剔除超时最大者，二元数据排序按照第一个开始排
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<pair<long long, long long>> a(n); // (d_i 排序用, t_i)
    for (int i = 0; i < n; ++i) {
        long long t, d;
        cin >> t >> d;
        a[i] = {d, t};
    }
    sort(a.begin(), a.end()); // 按 d_i 升序

    priority_queue<long long> pq; // 最大堆，存当前选中的 t_i
    long long T = 0; // 当前总工时
    for (auto& e : a) {
        long long d = e.first, t = e.second;
        pq.push(t);
        T += t;
        if (T > d) { // 超过当前截止时间，移除工时最大者
            T -= pq.top();
            pq.pop();
        }
    }
    cout << pq.size() << endl;
    return 0;
}