訓練4　叢林探險

題目描述（POJ2431）：一群人開著一輛卡車冒險進入叢林深處，卡車油箱壞了，每走1米就會漏1升油，他們需要到最近的城鎮（距離不超過106米）修理卡車?？ㄜ嚠斍拔恢煤统擎傊g有N（1≤N≤104）個加油站，每個加油站都可以加油1～100升，卡車油箱容量沒有限制。目前卡車距離城鎮L米，有P升油（1≤P≤106）。他們希望在前往城鎮的路上盡可能少地停下加油，請給出到達城鎮所需的最少加油次數。

輸入：第1行包含單個整數N，表示加油站的數量。第2..N+1行，每行都包含兩個整數，用于描述加油站，第1個整數是從城鎮到加油站的距離，第2個整數是該加油站的可用油量。第N+2行，每行都包含兩個整數L和P。

輸出：輸出到達城鎮所需的最少加油次數。若無法到達城鎮，則輸出-1。

題解：若在可以到達的距離范圍內有多個加油站，則將這些站點的加油量入隊（優先隊列）。若走到下一個加油站之前油會耗盡，則需要加油（優先隊列中最大加油量）后繼續走，當油量大于或等于卡車到城鎮的距離L時結束。

1. 完美圖解

在輸入樣例中，卡車距離城鎮25米，有10升油。沿著這條路，距離城鎮4、5、11和15米有4個加油站（可求出這些加油站距離卡車21、20、14和10米），這些加油站可分別提供多達4、2、5、10升的油。

求解的過程：因為卡車有10升油，所以首先開車10米，在第1個加油站加油10升，在第2個加油站加油5升，油箱的油量累計可到達距離25，可直接開車到鎮上。答案：停靠2次。

2. 算法設計

（1）按照距離降序排序。

（2）初始化。加油次數ans=0，當前可到達的位置pos=P，第k個站點k=0。

（3）若pos<L，則執行第4步；否則結束，輸出答案。

（4）若可到達的位置超過第k個加油站，則將第k個站點的加油量入隊（最大值優先），k++，一直循環到不滿足條件為止。

（5）若隊列為空，則輸出-1；否則加油（pos+=que.top();que.pop();ans++），轉向第3步。

3. 算法實現