题解 | #[JSOI2007]建筑抢修#

考察知识点：贪心、优先队列

读入每个建筑的信息，按照每个建筑修理的截止时间 t2 升序排序，然后依次将建筑修理的时间 t1 加入优先队列（大根堆），同时维护当前建筑修理的时间之和 time，当当前建筑修理完成后的时间大于截止时间时，如果当前建筑所需的修理时间 t1 小于优先队列顶端的建筑所需的修理时间（即最长修理时间）时，则将当前建筑与优先队列顶端的建筑交换，同时更新 time 为 time - pq.top() + t1，最后的优先队列大小即为最多可修理的建筑数量。

时间复杂度：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

void solve()
{
    int n;
    cin >> n;
    vpll t(n);
    for (int i = 0; i < n; i++)
    {
        ll t1, t2;
        cin >> t1 >> t2;
        t[i] = {t2, t1};
    }
    sort(t.begin(), t.end());
    priority_queue<ll, vl, less<ll>> pq; // 大根堆
    ll time = 0;
    for (int i = 0; i < n; i++)
    {
        ll t1 = t[i].second, t2 = t[i].first;
        if (time + t1 <= t2)
        {
            pq.push(t1);
            time += t1;
        }
        else if (!pq.empty() && pq.top() > t1)
        {
            time -= pq.top() - t1;
            pq.pop();
            pq.push(t1);
        }
    }
    cout << pq.size() << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}