宣告一個變數來累積距離
C++可以使用map儲存<油價, 可以跑到的距離>
每輸入一筆資訊,新增到map內
map會依照油價排序
從頭開始搜尋,將油價乘上距離累加起來,直到可以跑到的距離大於等於下一個加油站的距離
如果累積距離已經大於可以跑到的距離,可以把該筆資料erase掉
舉例
油箱的容量:40
加油站的數目:3
累積距離:0
map:空
2 10
map:{{2,40}}
距離0~10,只有2的油價可以用
所以累積花費=0+10*2=20
累積距離:10
1 15
map:{{1,50},{2,40}}
距離10~25,1的油價可以cover
所以累積花費=20+15*1=35
累積距離:25
2 30
map:{{1,50},{2,70}}
距離25~50,1的油價可以cover
所以累積花費=35+25*1=60
因為下一站的距離是55,所以 1的油價已經無法使用可以erase掉
map:{{2,70}}
距離50~55,2的油價可以cover
所以累積花費=60+5*2=70
累積距離:55