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 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告