[JSOI2007]建筑抢修 [贪心]+[堆的应用]

题意

一共有n个设施需要修复，给出每个设施修复需要的时长，和每个设施被修复好的最晚时间（deadline），求最多能修复好多少个设施。

题解

贪心，首先先将所有修复任务按照最晚时间由小到大排序，如果本题开始时间固定，那就直接按顺序计算即可（hdoj2037），但是因为每个设施的开始时间是弹性的，所以我们应该让每个修复任务开始时间尽量较早，故可以建立一个堆，保存每个修复的设施的修复时长，按顺序判断每个任务是否可以完成。

即：考虑第i个任务，
若满足已选择的任务所花费的时间+当前修复任务所需时间<=此任务截止时间则res+1,并将此修复任务所需时长压入堆中。
若不满足：则判断当前任务时长是否小于已选择任务中时长最长的那个，若是，则用时长较短的任务替换时长较长的任务，为后面的任务留出更充裕时间。

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

vector<pii> a;  //存储每个任务需要时间以及截止时间。
priority_queue<ll> pq;  //大根堆存储选择任务的时长

bool cmp(pii x,pii y){  //排序方式
    return x.second < y.second;
}

int main()
{
    int n;
    scanf("%d",&n);
    a.resize(n);
    for(int i = 0;i < n;++i)
        scanf("%lld%lld",&a[i].first,&a[i].second);
    sort(a.begin(),a.end(),cmp);    //按截止时间排序

    int res = 0;        //当前以选择任务
    ll now = 0;         //当前已选择任务的总时长
    for(int i = 0;i < n;++i){
        if(now + a[i].first <= a[i].second){    //若允许选择此任务
            pq.push(a[i].first);                //将任务时长压入堆中
            now += a[i].first;                  //更新总时长
            res++;                              //更新选择任务数量
        }
        else{
            if(!pq.empty() && a[i].first < pq.top()){   //满足当前任务所需时长更短
                int hd = pq.top();pq.pop();
                pq.push(a[i].first);
                now -= hd;                      //更新已选择任务以及总时长
                now += a[i].first;
            }
        }
    }
    printf("%d\n",res);
    return 0;
}