POJ 2431 Expedition：贪心 + 优先队列加油策略

题目大意

距离终点 L，初始油 P。沿途 N 个加油站（距离终点距离、油量）。每单位距离耗 1 油。求最少加油次数到达终点，不能到达输出 -1。

贪心策略

1. 将加油站按距离起点排序（输入给距终点距离，需转换）
2. 终点视为加油量 0 的站点
3. 行驶过程中，油不足时，从经过的站点中选油量最大的加（优先队列）

C++ 实现

#include 
#include 
#include 
using namespace std;

pair st[10100];
int N, P, L;

int main() {
    while (scanf("%d", &N) == 1) {
        for (int i=0;i pq;
        int ans = 0, pos = 0, fuel = P;
        for (int i=0; i<=N; ++i) {
            int dist = st[i].first - pos;
            while (fuel < dist) {
                if (pq.empty()) { ans = -1; break; }
                fuel += pq.top(); pq.pop(); ++ans;
            }
            if (ans == -1) break;
            fuel -= dist;
            pos = st[i].first;
            pq.push(st[i].second);
        }
        printf("%d\n", ans);
    }
    return 0;
}

关键细节

1. 坐标转换：输入距终点距离 → 距起点距离 = L - d
2. 终点入队：统一处理最后一段
3. 优先队列：大顶堆，总是选最大油量加

复杂度

• 排序 O(N log N)，堆操作 O(N log N)
• N ≤ 10000，极快