题目描述

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

第一行，D1​，C，D2，P，N。

接下来有 N 行。

第 i+1 行，两个数字，油站 i离出发点的距离 Di 和每升汽油价格 Pi。
输出格式

所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出 No Solution。
输入输出样例
输入 #1

275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2

输出 #1

26.95

说明/提示

N≤6，其余数字≤500。

这道题目应用贪心算法解

算法原理如下：

1.枚举途中经过的加油站，每经过一个加油站，计算一次花费；

2.在一个加油站所需要加的油，就是能够支持它到达下一个油价比它低的加油站的量；

3.如果在这个加油站即使加满油，都不能到达一个比它油价低的加油站，就把油箱加满，前往能够到达的加油站中油价最低的那个；

4.如果在这个加油站即使加满油，都不能到达任意一个加油站，也不能到达终点城市，说明无解；

第三点：为什么要加满油？因为这样可以减少在下一个贵的加油站所需要加的油量。