自动搬运

查看原文

来自洛谷，原作者为

	Night_sea_64 距离省选还有 +inf 天。

搬运于2025-08-24 23:09:09，当前版本为作者最后更新于2025-02-01 19:17:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先我们发现，走到某一个餐馆就直接决定是否用餐是不现实，因为不好预测后面的情况。所以能拖着就拖着，等到没能量了再去选择之前的餐馆。

而选择之前的餐馆时，餐馆位置就没用了，直接选择能量补充最多的。优先队列维护即可。

时间复杂度 $O(n\log n)$。

#include<iostream>
#include<queue>
#include<algorithm>
#define int long long
using namespace std;
int n,d,t;
struct node{int x,y;}a[200010];
bool cmp(const node &x,const node &y){
    return x.x<y.x;
}
priority_queue<int>q;
signed main()
{
    cin>>n>>d>>t;
    for(int i=1;i<=n;i++)cin>>a[i].x;
    for(int i=1;i<=n;i++)cin>>a[i].y;
    sort(a+1,a+n+1,cmp);
    a[++n]=(node){t,0};
    int cnt=0;
    for(int i=1;i<=n;i++)
    {
        d-=a[i].x-a[i-1].x;
        while(!q.empty()&&d<0)
        {
            d+=q.top(),cnt++;
            q.pop();
        }
        if(d<0)
        {
            cout<<-1<<endl;
            return 0;
        }
        q.push(a[i].y);
    }
    cout<<cnt<<endl;
    return 0;
}