【BZOJ1029】建筑抢修（贪心）

题面

BZOJ
洛谷

题解

感觉自己已经不会贪心了。
很明显的一个想法是按照终止时间排序，然后能选则选。
但是这样子可能会因为前面选择了一个修理时间很长的，导致现在这个不能选。
那么我们加一个大根堆，把所有已经选择的修理时间全部压进去。
如果当前这个不能选的话，检查是否能够减少修堆顶那个，来让现在这个能够被修。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define ll int
#define pi pair<ll,ll>
#define mp make_pair
#define fr first
#define sd second
inline ll read()
{
    ll x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
pi p[150100];
priority_queue<ll> Q;
int main()
{
    int n=read();
    for(int i=1;i<=n;++i)p[i].sd=read(),p[i].fr=read();
    sort(&p[1],&p[n+1]);
    ll nw=0;int ans=0;
    for(int i=1;i<=n;++i)
    {
        if(nw+p[i].sd<=p[i].fr)
            ++ans,Q.push(p[i].sd),nw+=p[i].sd;
        else
        {
            ll u=Q.top();
            if(u>p[i].sd)
                Q.pop(),Q.push(p[i].sd),nw-=u-p[i].sd;
        }
    }
    printf("%d\n",ans);
    return 0;
}

【BZOJ1029】建筑抢修（贪心）

原文：https://www.cnblogs.com/cjyyb/p/9439794.html