BZOJ1029: [JSOI2007]建筑抢修

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1029

Solution

考虑贪心，先按照T2排序，消除时间影响，再依次选T1。
这样显然有问题
注意到是因为T2小T1大的浪费时间，可以用一个大根堆维护已选的T1，每次加入建筑，
若可行，将T1加入堆，答案加一；
若不可行，比较T1和栈顶，若T1小于堆顶，则舍去堆顶，选择当前建筑，否则跳过。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll int
#define N 150010
using namespace std;
inline ll read(){
    char ch=getchar(); ll x=0,f=1;
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
inline void write(ll x){
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10); putchar(x%10+'0');
}
struct heap{
    ll v[N],size;
    ll empty(){return !size;}
    void up(ll x){for (;x>1&&v[x>>1]<v[x];x>>=1) swap(v[x],v[x>>1]);}
    void push(ll x){v[++size]=x; up(size);}
    ll top(){return v[1];}
    void down(ll fa){
        for (ll son=fa;;fa=son){
            if ((fa<<1)<=size&&v[fa<<1]>v[son]) son=fa<<1;
            if ((fa<<1|1)<=size&&v[fa<<1|1]>v[son]) son=fa<<1|1;
            if (son==fa) return; swap(v[fa],v[son]);
        }
    }
    void pop(){swap(v[1],v[size--]); down(1);}
}Q;
struct data{
    ll T1,T2;
    bool friend operator <(data x,data y){return x.T2<y.T2;}
    bool friend operator >(data x,data y){return x.T2>y.T2;}
}a[N];
ll n,now,ans;
int main(){
    n=read();
    for (ll i=1;i<=n;i++)
        a[i].T1=read(),a[i].T2=read();
    sort(a+1,a+1+n);
    for (ll i=1;i<=n;i++){
        if (now+a[i].T1<=a[i].T2){
            ans++;
            now+=a[i].T1;
            Q.push(a[i].T1);
        }else
        if (!Q.empty()&&Q.top()>a[i].T1){
            now-=Q.top()-a[i].T1;
            Q.pop(); Q.push(a[i].T1);
        }
    }
    write(ans);
}