洛谷P4053 [JSOI2007] 建筑抢修 题解

题目链接：P4053 [JSOI2007] 建筑抢修

题意：

cxy 在玩 JSOI 提供的一个称之为“建筑抢修”的电脑游戏：经过了一场激烈的战斗，T 部落消灭了所有 Z 部落的入侵者。但是 T 部落的基地里已经有 \(N\) 个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。现在的情况是：T 部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就报废了。你的任务是帮 cxy 合理的制订一个修理顺序，以抢修尽可能多的建筑。

输入格式：

第一行，一个整数 \(N\)。

接下来 \(N\) 行，每行两个整数 \(T_1,T_2\) 描述一个建筑：修理这个建筑需要 \(T_1\) 秒，如果在 \(T_2\) 秒之内还没有修理完成，这个建筑就报废了。

输出格式：

输出一个整数 \(S\)，表示最多可以抢修 \(S\) 个建筑。

对于 \(100 \%\) 的数据，\(1 \le N < 150000\)，\(1 \le T_1 < T_2 < 2^{31}\)。

经典的反悔型贪心，经典的爆零。

说实话我根据直觉就是选耗时尽可能短的

我们把所有的建筑按 \(T_2\) 排序，从前到后依次考虑每个建筑

如果可以修，就把它的 \(T_1\) 加入大根堆

如果修不了，就把之前修的时间太长的扔掉

因为当初不知道有这更好的选择

时间复杂度 \(O(n \log n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(2e5+15))

int n;
struct node{int t,r;}a[N];
priority_queue<int> q;
bool operator<(node a,node b){return a.r<b.r;}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++) 
        cin >> a[i].t >> a[i].r;
    sort(a+1,a+1+n);
    int res=0,cur=0;
    for(int i=1; i<=n; i++)
    {
        if(cur +  a[i].t <= a[i].r)
        {
            cur += a[i].t; ++res;
            q.push(a[i].t);
        }else if(!q.empty() && a[i].t < q.top())
        {
            cur += a[i].t - q.top(); q.pop();
            q.push(a[i].t);
        }
    }
    cout << res << '\n';
    return 0;
}