Luogu P2107 小Z的AK计划 堆贪心

好久不做这种题了。。。

---

存一下每个点的位置和时间，由于达到某个位置跟之前去哪里AK的无关，所以在时间超限后，可以用大根堆弹掉之前消耗时间最大的，来更新答案，相当于去掉之前花费最大的，直到时间不在超限。

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#define ll long long
#define R register ll
using namespace std;
inline ll g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
}
struct node{
    ll pos,t;
    bool operator <(const node& y) const{return pos<y.pos;}
}a[100010];
priority_queue <ll> q;
int n,ans,tot,cnt;
ll sum,m;
signed main() {
    n=g(),m=g();
    for(R i=1,pos,t;i<=n;++i) {
        pos=g(),t=g(); if(t>m||pos>m) continue;
        a[++cnt].pos=pos,a[cnt].t=t;
    } sort(a+1,a+cnt+1);
    for(R i=1;i<=cnt;++i) {
        sum+=a[i].t+a[i].pos-a[i-1].pos;
        q.push(a[i].t);++tot;
        while(sum>m) sum-=q.top(),q.pop(),--tot;
        ans=max(ans,tot);
    } printf("%d
",ans);
}

---

2019.04.24