用Python查找房屋和最近邮箱之间的最小总距离的程序

Z时代
2024-01-10
分类：综合

假设我们有一个名为houses 的数组并有另一个值k。这里的houses[i]代表街道上第i个房子的位置，我们必须在这条街上分配k个邮箱，并找到每个房子和它最近的邮箱之间的最小总距离。

因此，如果输入类似于房屋 = [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。

示例

让我们看下面的实现来更好地理解

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))