Python程序：查找将相同人数送往两个不同城市的最低成本

假设我们有一个名为costs的列表。其中costs[i]包含[c1, c2]，表示对第i个人来说，到达城市0的成本为c1，到达城市1的成本为c2。我们希望相同数量的人前往城市0和城市1，我们需要找到所需的最低成本。

因此，如果输入类似于costs = [[2, 6],[10, 3],[4, 9],[5, 8]]，则输出将为17，因为第0人和第2人将前往城市0，第1人和第3人将前往城市1，因此城市0的成本为2+4 = 6，城市1的成本为8+3 = 11，总成本为17。

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

  • s := 0
  • a := 一个新的列表
  • 对于costs中的每个对 (x, y)，执行以下操作：
    • s := s + x
    • 将 (y - x) 插入到列表a的末尾
  • 对列表a进行排序
  • 对于范围从0到floor(a的大小 / 2) - 1的i，执行以下操作：
    • s := s + a[i]
  • 返回s

示例

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

def solve(costs):
   s = 0
   a = []
   for x, y in costs:
      s += x
      a += (y - x,)
   a.sort()
   for i in range(len(a) // 2):
      s += a[i]
   return s

costs = [[2, 6],[10, 3],[4, 9],[5, 8]]
print(solve(costs))

输入

[[2, 6],[10, 3],[4, 9],[5, 8]]

输出

17

更新于：2021年10月18日

123 次浏览

启动您的职业生涯

完成课程获得认证

开始学习
广告