💡题解与思路

✅问题转化

将所有加油站的距离从“距离城镇”转化为“距离起点”，便于模拟卡车从当前位置向前行驶。

🧠核心思想：贪心 + 最大堆（优先队列）

按距离升序排序加油站（从起点开始）

使用一个最大堆（优先队列）记录走过的加油站中能提供的油量

模拟卡车前进的过程：

若当前油量不够走到下一个加油站，则从之前路过的加油站中挑油量最大的一次加油

若无油可加，直接输出 -1

每次加油次数累计，直到卡车到达城镇

📌状态变量

pos: 当前卡车位置（起点为 0）

fuel: 当前剩余油量

idx: 当前可达的加油站索引

pq: 最大堆，保存所有已到达但尚未使用的加油站油量

📈时间复杂度

排序：$O(N \log N)$

遍历：$O(N)$

每次加油操作堆操作：$O(\log N)$

总体复杂度：$O(N \log N)$，可接受

代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

const int maxn = 10010;
struct node
{
	int dist, fuel;
};
node position[maxn];

int n, L, P;

bool cmp(const node &a, const node &b)
{
	return a.dist > b.dist;
}



int main()
{
	
	while(scanf("%d", &n) != EOF)
	{
		priority_queue<int> heap;
		for(int i = 0; i < n; i++)
			scanf("%d %d", &position[i].dist, &position[i].fuel);
		sort(position, position + n, cmp);
		scanf("%d %d", &L, &P);
		int t = 0;
		heap.push(P);
		int index = 0;
		while(L > 0 && !heap.empty())
		{
			t++;
			int tmp = heap.top();
			heap.pop();
			L -= tmp;
			while(index < n && L <= position[index].dist)
				heap.push(position[index++].fuel);
		}
		printf("%d\n", L <= 0? t - 1: -1);
	}
	
	return 0;
}