自动搬运

查看原文

来自洛谷，原作者为

	Album 走了，再见。

搬运于2025-08-24 21:55:59，当前版本为作者最后更新于2020-05-04 22:04:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

更好的阅读：传送门

分析

一道简单的贪心题。

首先，我们需要把所有数按照$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