Python程式：查詢房屋與最近郵箱之間的最小總距離

假設我們有一個名為houses的陣列，還有一個值k。這裡houses[i]表示街道上第i個房屋的位置，我們需要在街道上分配k個郵箱，並找到每個房屋與其最近郵箱之間的最小總距離。

所以，如果輸入像houses = [6,7,9,16,22] k = 2，那麼輸出將是9，因為如果我們在7和18處放置郵箱，那麼每個房屋的最小總距離是|6-7|+|7-7|+|9-7|+|16- 18|+|22-18| = 1+0+2+2+4 = 9。

為了解決這個問題，我們將遵循以下步驟：

  • 對列表houses進行排序

  • 定義一個函式util()。它將接收idx、n、k作為引數

  • 如果k等於1，則

    • core := houses[(n + idx)/2的商]

    • 返回[|houses[i] - core| 對於每個i在idx到n的範圍內]的所有元素的總和

  • result := 無窮大

  • 對於i在idx到n的範圍內，執行以下操作

    • 如果n - i < k - 1，則

      • 退出迴圈

    • result := result和util(idx, i, 1) + util(i+1, n, k - 1)的最小值

  • 返回result

  • 從主方法執行以下操作

  • 返回util(0, houses的大小 - 1, k)

示例

讓我們看看以下實現以獲得更好的理解

def solve(houses, k):
   houses.sort()
   def util(idx, n, k):
      if k == 1:
         core = houses[(n + idx) // 2]
         return sum([abs(houses[i] - core) for i in range(idx, n + 1)])
      result = float('inf')
      for i in range(idx, n + 1):
         if n - i < k - 1:
            break
         result = min(result, util(idx, i, 1) + util(i+1, n, k - 1))
      return result
   return util(0, len(houses) - 1, k)

houses = [6,7,9,16,22]
k = 2
print(solve(houses, k))

輸入

[6,7,9,16,22], 2

輸出

9

更新於: 2021年10月6日

993 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告