# I-旅行家的预算¶

## 1、题目描述¶

### 输入描述:¶

第一行：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


#### 输出¶

26.95


### 备注:¶

N≤6,其余数字≤500


## 2、解题思路¶

• 使用贪心法，每次都从当前位置找下一个汽油价格小的加油站，如果找不到，就继续走
• 在当前加油站判断，是否需要加油，判断是否需要加油才能够行驶到下一个加油站或者价格更低的加油站
def solve(total_distance, capacity, gasoline_distance, gasoline_prices):
cost = 0.0
oil = 0.0
last_pos = 0
for index, (distance, price) in enumerate(gasoline_prices):
oil -= (distance - last_pos) / gasoline_distance
if oil < 0:
cost = -1
break
if price < 0:
break
next_tank = index + 1
for pointer in range(next_tank, len(gasoline_prices)):
if gasoline_prices[pointer][1] < price:
next_tank = pointer
break
oil_need = (gasoline_prices[next_tank][0] - distance) / gasoline_distance
oil_need = min(capacity, oil_need)
add_oil = oil_need - oil

if add_oil > 0:
cost += add_oil * price
last_pos = distance
if cost == -1:
print("No Solution")
else:
print("{:.2f}".format(cost))

prices = []
t, c, d, p, tanks = input().strip().split()

prices.append([0.0, float(p)])
for i in range(int(tanks)):
dis, tank_price = input().strip().split()
prices.append([float(dis), float(tank_price)])

prices.append([float(t), -1])

prices.sort()

solve(float(t), float(c), float(d), prices)