使用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相同，则
- 内核：=房屋[(n+idx)/2的商]
- 返回范围idx到n的每个i [|houses[i] – core|的元素之和])
result:=无穷大
对于i范围idx到n，做到
- 如果n-i < k-1，则
  - 从循环中退出
- result:=最小值的结果和util(idx，i，1) + util(i+1，n，k – 1)
返回结果
从主方法做如下操作：
返回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))