PAT (Advanced Level) To Fill or Not to Fill（貪心）

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax​ (≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; Davg​ (≤20), the average distance per unit gas that the car can run; and N (≤ 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi​, the unit gas price, and Di​ (≤D), the distance between this station and Hangzhou, for i=1,⋯,N. All the numbers in a line are separated by a space.

For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print ​<code>​The maximum travel distance = X​</code>​ where ​<code>​X​</code>​ is the maximum possible distance the car can run, accurate up to 2 decimal places.

結尾無空行

到達終點，輸出加油花費最小總油費；

不能到達終點，輸出能夠到達的最遠距離。

結果的輸出形式如題中輸出執行個體所示。

解此題采用的是貪心政策：

假設終點處存在一個加油站，其油價為0，所在位置即為終點的距離；

對所有的加油站按離起點的距離升序排序；

初始化車子目前所在的位置curDis,目前油價curPrice,總油價totalPrice,油箱剩餘的油可行駛的距離leftDis;

因車的油箱初始為空，若起點沒有加油站，則到達不了終點，行駛最大距離為0，此時輸出結果，否則轉第5步；

查找車子目前位置所能到達的最遠距離内的所有加油站，若存在加油站的油價比目前位置加油站油價低，則僅在此位置加足夠行駛到油價更低的加油站即可。否則找出能到達的加油站中油價最低的，在目前位置加滿油後再行駛到油價最低的加油站；

若最後車子按此中政策能到達終點加油站，則輸出總油價，否則輸出能夠行駛的最遠距離。

采用上述算法可保證車子總是以最低的代價加油。

　　

作者：凸雲​，轉載請注明原文連結​