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加油1单位后，汽车有2单位燃油，我们可以消耗2单位燃油前往城市2。现在油箱为空。在城市2加油2单位燃油后，我们可以消耗2单位燃油返回城市0。

  • 我们可以从城市2出发，加满2单位燃油，然后前往城市0。然后在城市0加油3单位燃油后，前往城市1，剩余1单位燃油。然后在城市1加油1单位燃油，现在有2单位燃油，可以前往城市2。

但是，我们不能从城市1出发，因为只有1单位燃油，而前往城市2需要2单位燃油。

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

  • n := fuel数组的长度
  • req := 一个大小为n的数组，并用0填充
  • 对于k从0到1，执行以下操作：
    • 对于i从n-1到0递减，执行以下操作：
      • nexti := (i + 1) mod n
      • req[i] := 0和req[nexti] + costs[i] - fuel[i]中的最大值
      • 如果(req[i] + fuel[i] 和 cap中的最小值) - costs[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))

输入

3, [3,1,2], [2,2,2]

输出

2

更新于：2021年10月23日

425 次浏览

启动您的职业生涯

完成课程后获得认证

开始
广告