求解汽车加油问题贪心法

汽车加油问题是一个经典的贪心算法问题，也被称为加油站问题。问题描述如下：

有一辆汽车要从起点出发到达终点，途中有若干个加油站，汽车行驶一定距离需要消耗一定的油量，且汽车的油箱有限，只能加满油才能出发。现在给定汽车的初始油量和行驶距离，求出汽车是否能到达终点，如果能，最少需要在哪些加油站加油。

解决这个问题的贪心策略是从起点开始依次遍历每个加油站，如果当前加油站可以到达终点，那么就不需要在该加油站加油，直接继续前往下一个加油站。如果无法到达终点，则需要在当前加油站加油，加足够的油量使汽车能够到达下一个加油站或者终点。

代码实现如下：

def min_refills(x, n, L, stops):
    num_refills = 0  # 加油次数
    current_refill = 0  # 当前加油站位置
    while current_refill <= n:
        last_refill = current_refill
        while current_refill <= n and stops[current_refill + 1] - stops[last_refill] <= L:
            current_refill += 1
        if current_refill == last_refill:
            return -1  # 无法到达终点
        if current_refill <= n:
            num_refills += 1  # 加油
    return num_refills

其中，x 表示汽车的初始油量，n 表示加油站的数量，L 表示汽车行驶的距离，stops 表示每个加油站距离起点的距离。函数返回值为汽车需要加油的次数，如果无法到达终点则返回 -1。

这个算法的时间复杂度为 O(n)，其中 n 表示加油站的数量，因为需要遍历每个加油站一次。