题解 P4053 【[JSOI2007]建筑抢修】

· · 题解

更好的阅读：传送门

分析

一道简单的贪心题。

首先，我们需要把所有数按照t_2进行升序排序，从而确定修理建筑的先后顺序。

但仅仅这样贪心不一定是最优的，需要在中途进行转正。

排序之后，我们从1到n遍历一遍建筑，确定这个建筑是否需要修理。

显然，如果可以在这个建筑报废之前修理好它，则一定修。

否则的话，则一定会报废一个建筑。显然，要报废的建筑的是修理时间最长的建筑。

剩下的详见代码注释。

Code[Accepted]

#include <bits/stdc++.h>

#define ll long long
#define I inline
#define N 150001

using namespace std;

struct Building{
    ll t1;
    ll t2;
}build[N];

bool cmp(Building a , Building b){
    return a.t2 < b.t2;
}

int n;
ll sum , ans;
priority_queue<ll > Q;    //采用优先队列维护耗时最长的建筑。

int main(){
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> build[i].t1 >> build[i].t2;
    }
    sort(build + 1 , build + 1 + n , cmp);
    for(int i = 1; i <= n; i ++){
        sum += build[i].t1;
        Q.push(build[i].t1);
        if(sum <= build[i].t2){     //如果可以修，就修。
            ans ++;
        }
        else{       //否则报废耗时最长的建筑。
            sum -= Q.top();
            Q.pop();
        }
    }
    cout << ans << "\n";

    return 0;
}

THE END