1478. Allocate Mailboxes¶
题目信息¶
- 题号:
1478
- 难度:
Hard
- 主题:
动态规划、中位数、区间划分
- 原题:
- 重点:
在数轴上放置恰好
k个邮箱,最小化每栋房屋到最近邮箱的距离总和;同一组房屋的最优邮箱位于中位数
题目重述¶
给定数轴上互不相同的房屋位置数组 houses 和整数 k。可以在数轴任意整数位置放置恰好 k 个邮箱。
每栋房屋使用距离最近的邮箱。请返回所有房屋到其最近邮箱的绝对距离之和的最小值。
1 <= houses.length <= 100,1 <= houses[i] <= 10^4,1 <= k <= houses.length。
自建示例¶
邮箱可服务一段相邻房屋:
输入:houses = [1,4,8], k = 2
输出:3
解释:在 1 和 4 之间为前两栋房屋放一个邮箱,距离和为 3;另一邮箱放在 8,总代价为 3。
邮箱数量等于房屋数量时距离为零:
输入:houses = [2,9], k = 2
输出:0
解释:可以在每栋房屋位置各放一个邮箱。