1478. Allocate Mailboxes

题目信息

题号:

1478

难度:

Hard

主题:

动态规划、中位数、区间划分

原题:

LeetCode 1478

重点:

在数轴上放置恰好 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
解释:可以在每栋房屋位置各放一个邮箱。