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

假设我们有一个名为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))

输入

[6,7,9,16,22], 2
输出结果
9

以上是 用Python查找房屋和最近邮箱之间的最小总距离的程序 的全部内容, 来源链接: utcz.com/z/360826.html

回到顶部