贪心旅行家的预算

解题思路:   这和一般的加油问题有不同，一般的加油问题是求最小加油次数，那么它每次在加油站加油都是加满只是应该在哪些个加油站加的问题，它的贪心点在于每一步只考虑当前的油量够不够行驶到下一个加油站，够就不加不够就加。而这题是求加油花的钱要最少，那么我们就是要尽可能在油价便宜的加油站加油，它的贪心点在于每一步都选择在能给第i段路程提供油的最便宜的加油站加油。

注意事项:'No Solution' 有坑捏宝宝们

参考代码:

D1,C,D2,P,N = map(float,input().split())
N = int(N)
MAXD = C * D2    # 满油行程
Di = [0]          # 加油站位置列表
Pi = [P]          # 加油站价格列表
for _ in range(N):
    x,y = map(float,input().split())
    Di.append(x)
    Pi.append(y)

Distance = []     # 每一段的距离
Petrol = []       # 每一段的油耗
for i in range(1,N+1):
    Distance.append(Di[i]-Di[i-1])
Distance.append(D1-Di[N])
for i in range(N+1):
    Petrol.append(Distance[i] / D2)

cost = 0
def solve():
    global cost
    if MAXD < max(Distance):
        print('No Solution')         #   中间是一个空格我服了这傻逼题复制是两个空格一直报格式错误
        return
    cost += Petrol[0] * Pi[0]
    for i in range(1,N+1):
        for j in range(i+1):
            if Di[i] - Di[j] < MAXD:
                temp_pi = Pi[j:i+1]    # 能给第i段路程提供油的加油站的价格列表
                temp_di = Di[j:i+1]
                break
        temp_petrol = Petrol[i]     # 第i段路程的剩余应加油量，开始加油咯
        while temp_petrol:       
            minpi = min(temp_pi)
            minindex = temp_pi.index(minpi)
            temp = (MAXD - (Di[i] - temp_di[minindex])) / D2
            if temp >= temp_petrol:
                cost += temp_petrol * minpi
                temp_petrol = 0
            else:
                cost += temp * minpi
                temp_petrol -= temp
            temp_pi.pop(minindex)
            temp_di.pop(minindex)
    print('{:.2f}'.format(cost))    # 这里实际上是五舍六入，参考 https://blog.csdn.net/doudou_nc/article/details/98507849

solve()