#27891: 解題思路


cse011417 (哈哈哈)

學校 : 國立臺中高級工業職業學校
編號 : 22273
來源 : [42.77.142.213]
最後登入時間 :
2024-03-20 11:49:15
e386. Bill的跑車沒油了 | From: [223.139.0.2] | 發表日期 : 2021-11-04 13:56

宣告一個變數來累積距離

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

 

 
ZeroJudge Forum