【P2107】小Z的AK计划（优先队列+贪心）

水一发优先队列的水题。。

这个题貌似以前有做过类似的。具体的方法是用大根堆辅助贪心算法得出正解。可以看出来，如果小Z走到了某个地方，那么他最远一定是到了这里，不可能有再走回来这种操作，因为很明显那样不是最优解。

然后我们基于刚才的考虑贪心，如果走的远近确定了，那么我们的选择一定是最小的那些店，维护一个大根堆，然后从小到大枚举位置，每枚举一次就入队一个数，如果当前的总和比疲劳值大了，就弹出队首元素。记得开longlong。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<iomanip>
#define re register
#define ll long long
using namespace std;
ll  n,m,ans,maxx,sum;
struct market
{
    ll x,t;
};
market a[1000001];
priority_queue<int> q;
inline bool cmp(market x,market y)
{
    return x.x<y.x;
}
int main()
{
    cin>>n>>m;
    for(re int i=1;i<=n;i++) {cin>>a[i].x>>a[i].t;}
    sort(a+1,a+n+1,cmp);
    ll k=0;
    while(k<n)
    {
        k++;
        if(a[k].x>=m)
        break;
        ll cnt=m-a[k].x;
        sum+=a[k].t;
        q.push(a[k].t);
        maxx++;
        while(sum>cnt)
        {
            sum-=q.top();
            q.pop();
            maxx--;
        }
        ans=max(maxx,ans);
    }
    cout<<ans;
}