POJ 2431 Expedition：優先隊列貪心解決加油站最少停靠問題

題目場景

卡車距城鎮 L 單位，初始油 P。路徑上有 N ≤ 10⁴ 個加油站，第 i 站距城鎮 dᵢ、供油 fᵢ。卡車每單位距離耗 1 油，油箱無容量上限。求到達城鎮最少加油次數，不能到達輸出 -1。

核心貪心策略：走到走不動時，回頭加「經過過的最大油量站」

• 將城鎮視為虛擬加油站 (0, 0)，所有站點按距城鎮距離 遞增 排序（即按距起點距離遞減）。
• 從起點出發，維護「已經過但未加油的站點油量」的 大根堆。
• 當前油 fuel，下一站距離 dist。若 fuel ≥ dist，直接開過去，fuel -= dist，將該站油量入堆。
• 若 fuel < dist，從堆取最大油量加油（fuel += max，次數 +1），重複直到 fuel ≥ dist 或堆空（輸出 -1）。

正確性直覺

每次被迫加油時，選「經過過的最大油量站」能讓後續行程最長，從而減少未來加油機會。這是經典「延遲決策 + 優先隊列」貪心證明。

完整流程（偽碼）

sort stations by distance to town ascending
stations.push_back({0, 0}) // town
fuel = P; ans = 0; prev = L; // prev: 上一站距起點距離
maxHeap pq;
for each station (d, f):
    dist = prev - d // 本段路程
    while fuel < dist:
        if pq.empty(): return -1
        fuel += pq.top(); pq.pop(); ans++
    fuel -= dist
    pq.push(f)
    prev = d
return ans

複雜度

• 排序 O(N log N)，堆操作總共 O(N log N)。
• 記憶體 O(N)。

常見坑點

• 輸入站點給的是「距城鎮距離」，需轉換為「距起點距離」或直接按題意從城鎮向外處理（原碼兩種寫法均可）。
• 終點虛擬站油量為 0，確保最後一段也被處理。
• 若初始 P ≥ L，迴圈不進入 while，直接返回 0。

總結

本題是「優先隊列貪心」的教科書級應用：將「未來決策」延遲到「被迫執行」時刻，並用堆快速取最優歷史選項。同類問題包括「會議室安排」、「項目選擇」等，核心模式極具通用性。