用于查找我们可以在 Python 中开始旅行的起点数量的程序
假设有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