| layout | title | date | tags | |||
|---|---|---|---|---|---|---|
post |
[POJ] 2431 - Expedition |
2012-02-08 |
|
題目網址：2431 - Expedition
一群「牛」開著卡車在叢林中冒險，由於道路險峻，不小心把燃料箱給刺破了。導致每移動一單位的距離，就會漏一單位的燃料。現在他們要將卡車開往距離叢林 L 單位的城市修理，而現在卡車剩下 P 單位的燃料。在前往城市的路上會有 N 個燃料補給站，每個補給站可供應 Fi 單位的燃料，而卡車的燃料箱可以補充至無限量的燃料。現在要求求出抵達城市的路途中，最少需要停留補給站的次數。
- 補給站數量 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 中的元素被取盡，仍無法前進下一站，即表示無解。
<script src="https://gist.github.com/KuoE0/1789738.js"></script>Time Complexity: O(N × log N)
Source code on gist.