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

· · 题解

由于本人过于蒟蒻，遇到自己觉得有意思的题才会写题解，不足请见谅

我的做法↓

贪心+优先队列

由标签得贪心。

这道题我是在二叉堆的题单里找到的，首先想到用二叉堆。但二叉堆题单里的其他题，我都是用优先队列的（真的简单又方便），所以这题也不会例外。

首先联想到贪心算法的经典应用：选择不相交区间问题。

选择不相交区间问题

给定n个开区间(ai,bi)，选择尽量多个区间，使这些区间两两没有公共点。

一本通提高篇给出的思路

按照结束时间b1<=b2<=...<=bn的顺序排序，依次考虑各个活动，如果没有和已经选择的活动冲突，就选；否则就不选。

这题和上述问题的联系

本题中给出的T1,T2便可以转化为上述问题的线段，T2就是线段的右端点，T1就是线段的长度，由于题目不需要，所以不用算出左端点。

同样，按结束时间排序，依次考虑建筑。若当前能建，我们都建；若不能建，则在当前和原先建好的建筑里放弃T1最大的建筑，也就是放弃性价比最低的。而放弃最大的，就可以利用优先队列，弹出队尾元素。

CODE

#include <bits/stdc++.h>//蒟蒻只会万能头
using namespace std;

inline int gin(){//快读
    char c=getchar();
    int s=0,f=1;
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<3)+(s<<1)+(c^48);
        c=getchar();
    }
    return s*f;
}

struct node{//利用结构体，方便存储转化后的“线段”
    int t1,t2;
}a[150001];

bool cmp(node a,node b){//之后排序的cmp，优先考虑T2，若T2相同再考虑T1
    if(a.t2==b.t2)return a.t1<b.t1;
    return a.t2<b.t2;
}

int n,k=0,ans=0;
priority_queue<int,vector<int>,less<int> >q;
//优先队列，使用less<int>，是为了让弹出的元素最大

int main(){
    n=gin(); 
    for(int i=1;i<=n;i++){
        a[i].t1=gin(),a[i].t2=gin();        
    }
    sort(a+1,a+n+1,cmp);

//下面循环中的k，为当前时刻，可以理解为now
    for(int i=1;i<=n;i++){
        if(k+a[i].t1<=a[i].t2){//若当前能建
            ans++;  
            k+=a[i].t1;
            q.push(a[i].t1);
            continue;
        }
//接下来考虑不能建
        if(q.empty() || q.top()<=a[i].t1)continue;//若队列为空，或者队尾比当前性价比低，则直接放弃当前建筑
        k=k+a[i].t1-q.top();//放弃性价比最低的并且建造当前的，改变当前时刻
        q.pop();
        q.push(a[i].t1);
    }   
    printf("%d",ans);   
    return 0;
}