题意描述

小刚在玩~~JSOI~~提供的一个称之为“建筑抢修”的游戏。

经过了一场激烈的战斗，$T$部落消灭了所有$Z$部落的入侵者。

但是$T$部落的基地里已经有$N$个建筑设施受到了严重的损伤，如果不尽快修复的话，这些建筑设施将会完全毁坏。

现在的情况是：$T$部落基地里只有一个修理工人，虽然他能瞬间到达任何一个建筑，但是修复每个建筑都需要一定的时间。

同时，修理工人修理完一个建筑才能修理下一个建筑，不能同时修理多个建筑。

如果某个建筑在一段时间之内没有完全修理完毕，这个建筑就会报废。

你的任务是帮小刚合理的制订一个修理顺序，尽可能多的抢修建筑。

输入格式

第一行是一个整数$n$，表示建筑的数目。

接下来$n$行每行两个整数$t_1,t_2$，用来描述一个建筑：修理这个建筑需要$t_1$秒，如果在$t_2$秒之内还没有修理完成，这个建筑就报废了。

输出格式

输出只有一行，一个整数$s$，表示最多可以抢修的建筑数.

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围和约定

对于$100\%$的数据，$0 < N < 1.5 \times 10^5$， $0 < t_1 < t_2 < 2147483647$

分析

一道简单的贪心题。

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

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

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

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

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

剩下的详见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#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;
}