题目描述

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

输入格式

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

输出格式

输出一个整数S，表示最多可以抢修S个建筑.

输入输出样例

输入 #1

4
100 200
200 1300
1000 1250
2000 3200

输出 #1

3

题解

贪心
$t_i$: 修复 i 所花时间

$limit_i$: 在什么时候建筑 i 自爆

贪心策略：
按 $limit_i$ 从小到大排序之后，开始轮流遍历每个建筑。
如果中途某个建筑 i 无法在 $limit_i$ 的时间内修复，那么在先前选择修复的建筑中拿出 $t_j$最大的 $j$ 号建筑。若$t_i < t_j$ ，则放弃 $j$ 转而修 $i$。
策略证明:
若第 $i$ 号出现时间不足，那么前 $i$ 个建筑中最多修复 $i-1$ 个建筑，则我们必然选择 $t_i$较小的前 i-1 个建筑，给后面的修复留下更多的时间。

实现方法:
使用堆来维护选择的建筑 $t_i$最大的建筑

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<map>
#include<queue>
#include<sstream>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>
using namespace std;
#define ios ios::sync_with_stdio(false)
const double pi=acos(-1.0);
int dx[]={-1,0,1,0,0},dy[]={0,1,0,-1,0};
typedef long long LL;
typedef pair<LL,LL> PII;
const int INF=0x3f3f3f3f;
const LL IINF=0x3f3f3f3f3f3f3f3f;

const int N=150010;
struct Node
{
    LL t,limit;
    bool operator<(const Node &W) const
    {
        return limit<W.limit;
    }
}a[N];
int n;

int main()
{
    ios;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].t>>a[i].limit;
    sort(a+1,a+n+1);

    priority_queue<LL> heap;
    LL sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i].t;
        heap.push(a[i].t);

        if(sum > a[i].limit)
        {
            sum-=heap.top();
            heap.pop();
        }
    }

    cout<<heap.size()<<endl;
    // system("pause");
}