【每日一题】【5月26日】[JSOI2007]建筑抢修

题意：

个建筑，每个建筑有完成的持续时间 ，以及截止时间 。
同一时间只能抢修一个建筑，每个建筑需要在截止时间前完工，否则就报废。
问最多能有多少建筑抢修成功。

题解：

贪心。
先按截止时间排序。
然后顺序抢修，能抢修成功的则抢修。同时维护一个优先队列/堆，堆里存放抢修成功的建筑的持续时间。当不能抢修成功的时候，比较当前建筑的持续时间与堆顶元素（最大值），若当前值更小，则替换之。

Code:

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
using ll = long long;
struct Node {
    int t1, t2;
    Node() { }
    Node(int _t1, int _t2): t1(_t1), t2(_t2) { }
    bool operator < (const Node &t) const {
        return t2 < t.t2;
    }
}a[N];
int n;
priority_queue<int> q;
ll T0 = 0, ans = 0;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i].t1 >> a[i].t2;
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) {
        if(T0 + a[i].t1 <= a[i].t2) {
            T0 += a[i].t1; q.push(a[i].t1);
            ans++;           
        } else if(!q.empty() && q.top() > a[i].t1) {
            T0 -= q.top(); q.pop();
            T0 += a[i].t1; q.push(a[i].t1);
        }
    }
    cout << ans << endl;
    return 0;
}