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 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告