用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
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短