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