假设有 n 个城市，编号从 0 到 n-1，有 n 条有向道路。我们可以从城市 i 到城市 (i + 1) % n [0 到 1 到 2 到 .... 到 N - 1 到 0]。我们有车。我们汽车油箱的容量是盖单位。在城市 i 的开头，我们可以使用燃料 [i] 单位的燃料，汽车需要 cost[i] 单位的燃料从城市 i 行驶到 (i + 1) % n。我们必须找到有多少个城市可以启动我们的汽车，以便我们可以环游所有城市并到达起点的同一个城市？
因此，如果输入类似于 cap = 3 燃料 = [3,1,2] 成本 = [2,2,2]，那么输出将为 2，因为有两种可能的解决方案。
我们可以从 0 号城市开始，给油箱加满 3 个单位的燃料，然后用 2 个单位的燃料行驶到 1 号城市。Tank 还剩 1 个单位。在城市 1 消耗 1 个单位的燃料后，汽车有 2 个单位的燃料，我们可以使用 2 个单位的燃料行驶到城市 2。现在油箱是空的。在城市 2 加油 2 加仑燃料后，我们然后使用 2 加仑燃料返回城市 0。
我们可以从2号城市出发，给汽车加满2单位的油，然后行驶到0号城市，然后从0号城市加满3加仑的油，然后再行驶到1号城市，我们就有1单位的油了。然后我们可以在城市 1 加油 1 单位的燃料，现在有 2 单位的燃料并前往城市 2。
但是，我们不能从城市 1 开始，只有 1 个单位的燃料存在，但前往城市 2 需要 2 加仑。
让我们看看以下实现以获得更好的理解 -
def solve(cap, fuel, costs): n = len(fuel) req = [0] * n for k in range(2): for i in range(n-1, -1, -1): nexti = (i + 1) % n req[i] = max(0, req[nexti] + costs[i] - fuel[i]) if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]: return 0 return sum(1 for r in req if r == 0) cap = 3 fuel = [3,1,2] costs = [2,2,2] print(solve(cap, fuel, costs))
3, [3,1,2], [2,2,2]输出结果
2