用 Python 编写程序，查找我们可以从中开始旅行的起点数量

pythonserver side programmingprogramming更新于 2026/1/30 15:40:17

假设有 n 个城市，编号从 0 到 n-1，有 n 条有向道路。我们可以从城市 i 前往城市 (i + 1) % n [0 到 1 到 2 到 .... 到 N - 1 到 0]。我们有一辆汽车。我们汽车的油箱容量为 cap 单位。在城市 i 的起点处我们可以使用 fuel[i] 单位的燃料，汽车从城市 i 前往 (i + 1) % n 需要 cost[i] 单位的燃料。我们必须找出有多少个城市可以从哪里出发，这样我们就可以绕着所有城市行驶并到达出发的同一个城市?

因此，如果输入为 cap = 3 fuel = [3,1,2] cost = [2,2,2]，则输出将为 2，因为有两种可能的解决方案。

我们可以从城市 0 出发，用 3 单位燃料加满油箱，然后使用 2 单位燃料前往城市 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 加仑。

为了解决这个问题，我们将遵循以下步骤 −

n := 燃料大小
req := 大小为 n 的数组并用 0 填充
对于 k 在 0 到 1 的范围内，执行
- 对于 i 在 n-1 到 0 的范围内，减少 1，执行
  - nexti :=(i + 1) mod n
  - req[i] := 最大值 0 和 req[nexti] + cost[i] - fuel[i]
  - 如果 (req[i] + fuel[i] 和 cap) - cost[i] < req[nexti] 中的最小值，则
    - 返回 0
返回 r 中 0 的个数

示例

让我们看看下面的实现以便更好地理解 −

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))