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

题意：

从n栋楼里修楼 每栋楼有修理时间和截止时间 问最多能修多少栋楼

思路：

贪心是肯定的。我们先按结束时间排序，结束时间越早 你就可以干越多的事 其次按消耗时间排序 但是会存在性价比更高的方式 前面消耗时间太长 导致后面可以有更多的选项没有选到 采用开个堆 反悔贪心一手 如果我当下无法选择这个修这个楼 就看看前面的选择 有没有比当下选择消耗时间更多的 有的话明显当下的选择是更优的 替换一下 这样最终答案就是正确的

代码

#include <bits/stdc++.h>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define mes(x, a) memset(x, a, sizeof(x));
#define sca(a) scanf("%d", &a)
#define lowbit(x) x&(-x)
#define mk make_pair
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define lson v << 1
#define rson v << 1 | 1
#define pii pair<int, int>

const int N = 150005;

struct node{
    int x,t;
}a[N];

bool cmp(node a,node b){
    if(a.t != b.t){
        return a.t < b.t;
    }
    return a.x < b.x;
}


priority_queue <int> q;

int main(){
    ios::sync_with_stdio(0);

    int n;cin >> n;

    for(int i = 1;i <= n;i ++){
        cin >> a[i].x >> a[i].t;
    }

    sort(a + 1,a + 1 + n,cmp);

    LL time = 0;

    int  res = 0;

    for(int i = 1;i <= n;i ++){
        if(time + a[i].x <= a[i].t){
            res ++ ;
            time += a[i].x;
            q.push(a[i].x);
        }else{
            if(a[i].x < q.top()){
                time -= q.top();
                time += a[i].x;
                q.pop();
                q.push(a[i].x);
            }
        }
    }


    cout << res << '\n';

    return 0;
}