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步；

查找车子当前位置所能到达的最远距离内的所有加油站，若存在加油站的油价比当前位置加油站油价低，则仅在此位置加足够行驶到油价更低的加油站即可。否则找出能到达的加油站中油价最低的，在当前位置加满油后再行驶到油价最低的加油站；

若最后车子按此中策略能到达终点加油站，则输出总油价，否则输出能够行驶的最远距离。

采用上述算法可保证车子总是以最低的代价加油。

　　

作者：凸云​，转载请注明原文链接​