在 Python 中查找可以开始旅行的起始点数量的程序

假设有 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]，costs = [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 填充
for k in range 0 to 1, do
- for i in range n-1 to 0, decrease by 1, do
  - nexti := (i + 1) mod n
  - req[i] := 0 和 req[nexti] + costs[i] – fuel[i] 的最大值
  - 如果最小值 (req[i] + fuel[i] 和 cap) – costs[i]< req[nexti]，则
  - 返回 0
return 在 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))