用 Python 编写程序，查找房屋与最近邮箱之间的最小总距离

pythonserver side programmingprogramming更新于 2025/11/30 16:44:17

假设我们有一个名为 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[quotient of (n + idx)/2]
- 返回 [|houses[i] - core| 的所有元素之和for each i in range idx to n])
result := infinity
对于 idx 到 n 范围内的 i，执行
- 如果 n - i < k - 1，则
  - 退出循环
- result := minimum of result and util(idx, i, 1) + util(i+1, n, k - 1)
返回 result
从主方法执行以下操作:
返回 util(0, size of 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))