[JSOI2007]建筑抢修（贪心，优先队列）

题目：

有n个建筑待修理。修理第i个建筑用时，修理它的截止日期是。只有在截止日期前修好某个建筑才算修好。现在问最多能修好多少个建筑。

做法：

这题是个贪心。
我们将截止日期排序。从前往后处理。当前修建筑的总用时时，选择修第i个建筑，
而当时。我们就看需不需要用当前的建筑替换之前修过的建筑。很显然如果之前有一个建筑修理用时比当前建筑长，我们替换它后能在保证修理数量不减的情况下使当前修理总用时变小，这当然是更优的的做法。而替换掉之前修理用时最长的建筑，是最优解。
这个贪心过程用优先队列维护一下就行了。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
struct node{
    ll t1, t2;
    bool operator < (const node& rh)const{
        if (t2 != rh.t2) return t2 < rh.t2;
        return t1 < rh.t1;
    }
}a[N];
int main(void){ 
    IOS;
    int n; cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i].t1 >> a[i].t2;
    } 
    sort(a+1, a+n+1);
    priority_queue<ll> q;
    ll now = 0;
    int ans = 0;
    for (int i = 1; i <= n; ++i){
        if (now+a[i].t1 <= a[i].t2){
            now += a[i].t1, ans++;
            q.push(a[i].t1);
        }else{
            if (q.top() > a[i].t1){
                now -= q.top(); q.pop();
                q.push(a[i].t1);
                now += a[i].t1;
            }
        }
    }
    cout << ans << endl;
    return 0;
}