網頁

2014年3月2日 星期日

POJ 2431 Expedition

題意:
  一群牛從起點要出發到城鎮(目的地)距離共L單位,每走一單位同時消耗一單位的油,一開始油箱有P單位的油量,路途中會經過幾個加油站,每個加油站會給兩個數字,1.距離城鎮多少單位,2.這個加油站能加多少油,本題問到目的最少要到幾個加油站加油,如果不可能到達目的地則輸出-1。

想法:
  因為所有地點都在同一直線上,所以都會經過每個加油站,只是看要不要停下來加油而已。所以我們就盡可能往前走,把每個路過加油站的該站的加油量放到priority queue裡面,然後直到走到途中沒油了,就從priority queue裡面拿出第一個(最大的加油量)加到自己的油箱,因為既然要加油,就要一次加最多的油,一直反覆這個動作直到終點。