旅行家的预算 解题报告

问题描述：

Problem description
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）．每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距Di、每升汽油价格 Pi（ i＝l，2，...N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No solution”。

Input
输入数据的第一行是四个实数；
D1 C D2 P分别表示两个城市之间的距离，汽车油箱的容量，每升汽油能行驶的距离，出发点每升汽油价格；
第二行是一个整数N,沿途的油站数。
第三行到第N+2，每一行是一个油站的基本信息描述，包括该油站离出发点的距离，该油站每升汽油的价格。

Output
输出到达目的城市的最小费用(四舍五入到两位小数)，若不能到达目的城市则输出 No solution

Sample Input
275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2

Sample Output
26.95

假设现在在第i站，那么在这站加满油可以到达的最远距离是dis[i]+c*d2，

如果在这个范围内存在一个加油站j，它的价格pri[j]<pri[i]，那么只要把油加到刚好能到达j就可以了；

如果在这个范围内不存在这样的加油站，那么就在i加满油，然后走到尽量远的加油站j，如果无法走到j，即最近的加油站dis[j]>dis[i]+c*d2，此时无解。

这是别人的算法，我的问题是：当所能到达的范围内没有比当前加油站更便宜的，为什么要走到最远的那个去加，而不是在中间这些加油站中最便宜的那个？

问题解答：

旅行家的预算 解题报告这个旅游问答期待您的解答，请登录账号或关注微信公众号回答这个问题。