洛谷4053 [JSOI2007]建筑抢修

题意

有 $n(\le 150000)$ 个建筑需要修复，每个建筑有修复耗时 $t1$ 以及修复完成的截止时间 $t2$ ，问最多能修复多少个建筑。

题解

贪心。先把所有建筑按照截止时间排序，然后依次处理各个建筑。如果当前建筑还能修就修，否则就从之前修过的建筑里找到耗时最多的，如果比当前建筑的耗时多就替换掉。需要用堆维护。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=150005;
struct node {
    int t1,t2;
} s[N];
int n;
priority_queue <int> q;

inline bool cmp(node x,node y) { return x.t2<y.t2; }

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i].t1=read(),s[i].t2=read();
    sort(s+1,s+n+1,cmp);
    int ans=n,cur=s[1].t1;
    q.push(s[1].t1);
    for (int i=2;i<=n;i++)
    {
        if (cur+s[i].t1<=s[i].t2) //能修就修
        {
            cur+=s[i].t1;
            q.push(s[i].t1);
        }
        else
        {
            ans--;
            if (q.top()>s[i].t1) //替换
            {
                cur-=q.top()-s[i].t1;
                q.pop(); q.push(s[i].t1);
            }
        }
    }
    return !printf("%d",ans);
}