用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