题解：P11650 [COCI 2024/2025 #4] 力 / Benzinska

Night_sea_64 · 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;
}