題目網址：2431 - Expedition

題目概述

一群「牛」開著卡車在叢林中冒險，由於道路險峻，不小心把燃料箱給刺破了。導致每移動一單位的距離，就會漏一單位的燃料。現在他們要將卡車開往距離叢林 L 單位的城市修理，而現在卡車剩下 P 單位的燃料。在前往城市的路上會有 N 個燃料補給站，每個補給站可供應 Fi 單位的燃料，而卡車的燃料箱可以補充至無限量的燃料。現在要求求出抵達城市的路途中，最少需要停留補給站的次數。

Technique Detail

  • 補給站數量 N，2 ≤ N ≤ 10,000
  • 與城市的距離 L，0 ≤ L ≤ 1,000,000
  • 現存燃料 P，1 ≤ P ≤ 1,000,000
  • 補給站可補給的燃料 Fi，1 ≤ Fi ≤ 100

輸入格式

對於每筆測試資料的第一行輸入一個整數 N，表示補給站數量。接下來有 N 行，每行兩個整數 Xi, Fi，表示第 i 個補給站距離城市 Xi 單位，且該補給站僅能提供 Fi 單位的燃料。最後再一行，包含兩個整數 L, P，表示城市距離叢林 L 單位，卡車目前剩下 P 單位的燃料。

輸出格式

對於每一筆測試資料，輸出一個整數，表示最少停留次數。若無解時，請輸出 -1。

解題思路

每移動一單位就會漏一單位的燃料，其實就是說，只要燃料箱的燃料量有 L 單位，那麼即可從叢林抵達城市。

把終點的城市也當作一個補給站，到達最後一個補給站前所需要停留的最少次數，也基於到上一個補給站所需要的最少次數，並判斷是否需要多停留。

因此由初始的燃料量開始，判斷該燃料量可以最遠可以抵達哪個燃料站，並記錄下沿途所經過的燃料站所能提供的燃料量。若以無法抵達下一個燃料站或終點，開始從記錄下的燃料量中取出最大的，並標示為停靠燃料站一次。若仍無法抵達下一個燃料站或終點，在從記錄中的燃料量中取出最大值，直到可以抵達下一個燃料站或終點。再繼續前進至燃料用完，並依照先前取用燃料的方式直到抵達終點。若所有記錄下的燃料量都被取用完仍無法抵達，表示不存在叢林到都市的情況。

實際的作法為，將所有燃料站依照位置排序。接著開始移動卡車，並將經過的燃料站的燃料量丟入 priority queue，當無法抵達下一站時，就開始從priority queue 中取出最大值，直到燃料量足夠抵達下一站。如此重複該步驟直到抵達終點即可，若 priority queue 中的元素被取盡，仍無法前進下一站，即表示無解。

Time Complexity: O(N × log N)

Source Code

Source code on gist.