题解 P4053 【[JSOI2007]建筑抢修】

红色OI再临 · 2019-10-21 07:59:08 · 题解

很经典的可反悔类贪心呢

可反悔类贪心：先在符合情况下尽量做出当前最优的决策，如果不符合，则将之前做出的代价较大的决策替换为当前决策，通常使用堆

对于这道题目，先让结尾时间排序，然后对于一个建筑，如果在结尾时间能修就修，如果不能，就从修之前的修筑时间大的建筑替换修当前建筑，就实现了可反悔

思路就酱~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define re register int
#define maxn 1000050
using namespace std;
int now;
struct node{
    int t1,t2;
}t[maxn];
priority_queue<int>q;
int n,m;
bool comp(node aa,node bb){
    return aa.t2<bb.t2;
}
int main(){
    scanf("%d",&n);
    for(re i=1;i<=n;i++){
        scanf("%d%d",&t[i].t1,&t[i].t2);
    }
    sort(t+1,t+1+n,comp);
    int cnt=0;
    for(re i=1;i<=n;i++){
        if(now+t[i].t1>t[i].t2){
            if(t[i].t1<q.top()){
                int u=q.top();
                q.pop();
                now-=u;
                q.push(t[i].t1);
                now+=t[i].t1;
            }
        }
        else {
            cnt++;
            now+=t[i].t1;
            q.push(t[i].t1);
        }
    }
    printf("%d\n",cnt);
    return 0;
}