POJ 2431 Expedition：優先隊列貪心解決加油最少停靠次數

題目背景

卡車距離終點 L，初始油量 P。路徑上有 N 個加油站，每站距離終點 dis、提供油量 fuel。卡車每單位距離消耗 1 單位油，油箱無容量上限。求到達終點最少加油次數，不可達輸出 -1。

核心洞察：貪心 + 最大堆

1. 將加油站距離轉換為相對起點距離：dis = L - dis，並按距離升序排序。
2. 將終點視為油量為 0 的加油站加入數組。
3. 行駛過程中，將經過的加油站油量存入**最大堆**。
4. 當當前油量不足以到達下一站時，從堆中取出最大油量加油（次數 +1），直到油量足夠或堆空（不可達）。

正確性證明

為了最小化加油次數，每次應選擇當前可達範圍內油量最大的站點加油。最大堆恰好提供此操作，貪心策略最優。

完整代碼

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int MAX = 1e4 + 5;
struct Stop { int dis, fuel; } s[MAX];
bool cmp(Stop a, Stop b) { return a.dis < b.dis; }

int main() {
    int n, l, p;
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) scanf("%d %d", &s[i].dis, &s[i].fuel);
        scanf("%d %d", &l, &p);
        for (int i = 0; i < n; i++) s[i].dis = l - s[i].dis;
        s[n].fuel = 0; s[n++].dis = l; // 終點入隊
        sort(s, s + n, cmp);
        priority_queue<int> q;
        int ans = 0, pos = 0, fuel = p;
        for (int i = 0; i < n; i++) {
            int d = s[i].dis - pos;
            while (fuel < d) {
                if (q.empty()) { printf("-1\n"); goto END; }
                fuel += q.top(); q.pop(); ans++;
            }
            fuel -= d;
            q.push(s[i].fuel);
            pos = s[i].dis;
        }
        printf("%d\n", ans);
        END: ;
    }
    return 0;
}

關鍵細節

• 輸入加油站不保證有序，**必須排序**。
• 終點作為特別加油站處理，統一邏輯。
• goto END 簡化多層循環跳出，實際可用標誌變量替代。

複雜度

• 排序：O(N log N)
• 堆操作：每站進堆一次、出堆至多一次，O(N log N)
• 總體：O(N log N)，N ≤ 10,000 極快。