前言

一看就是贪心，想到了 P9749 [CSP-J 2023] 公路 ，异曲同工之妙啊。

分析

算法

贪心策略：每次在能量不足时，从已到达的餐馆中选择能量最大的进行用餐，最小化总用餐次数。

反证贪心，假设存在一个最优解，其中某一步未选择当前最大的能量 $y_{max}$ ，而选择了较小的 $y_{min}$ 。由于 $y_{max}>y_{min}$ ，选择 $y_{max}$ 能提供更多能量，可能减少后续的用餐次数。因此，原解可以替换为选择 $y_{max}$ ，且替换后的解不会更差，与原假设矛盾。

综上，最优解中每一步的选择必然是当前可用的最大补充量，贪心成立。

具体实现

先把餐馆按位置 $x_i$ 升序排序。然后使用优先队列维护可用的能量。若当前能量不足，从堆中取出最大补充量进行用餐，直到能量足够或堆为空。

若堆为空仍无法满足能量需求，则无解。

时间复杂度：$O(n \log n)$ ，可以通过本题。

AC Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
int n,d,X,ans;
priority_queue<int> pq; //优先队列维护可用的能量增量
struct node 
{
    int x,y;
}a[maxn];
bool cmp(node a,node b) //按位置 x 升序排序
{
    return a.x<b.x;
}
int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n>>d>>X;
    int sum=d,pos=0; //sum记录当前能量  pos记录当前位置 
    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);
    for(int i=1;i<=n;i++) 
	{
        int dis=a[i].x-pos;
        if(sum<dis) 
		{
            //能量不足时
            while(!pq.empty()&&sum<dis) 
			{
                sum+=pq.top();
                pq.pop();
                ans++;
            }
            if(sum<dis) 
			{
                //无解
                cout << -1 << endl;
                return 0;
            }
        }
        sum -= dis;
        pos = a[i].x;
        pq.push(a[i].y);
    }
    //处理从最后一个餐馆到终点的距离
    int dis=X-pos;
    if(sum<dis) 
	{
		//同上 
        while(!pq.empty()&&sum<dis) 
		{
            sum+=pq.top();
            pq.pop();
            ans++;
        }
        if(sum<dis) 
		{
			//同上
            cout<<-1;
            return 0;
        }
    }
    cout<<ans;
    return 0;
}