【动态规划】【中位数贪心】【C++算法】1478. 安排邮筒

# 作者推荐

【���度优先搜索】【树】【图论】2973. 树中每个节点放置的金币数目

本文涉及知识点

动态规划汇总

LeetCode1478. 安排邮筒

给你一个房屋数组houses 和一个整数 k ，其中 houses[i] 是第 i 栋房子在一条街上的位置，现需要在这条街上安排 k 个邮筒。

请你返回每栋房子与离它最近的邮筒之间的距离的 最小 总和。

答案保证在 32 位有符号整数范围以内。

示例 1：

输入：houses = [1,4,8,10,20], k = 3

输出：5

解释：将邮筒分别安放在位置 3， 9 和 20 处。

每个房子到最近邮筒的距离和为 |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 。

示例 2：

输入：houses = [2,3,5,12,18], k = 2

输出：9

解释：将邮筒分别安放在位置 3 和 14 处。

每个房子到最近邮筒距离和为 |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9 。

示例 3：

输入：houses = [7,4,6,1], k = 1

输出：8

示例 4：

输入：houses = [3,6,14,10], k = 4

输出：0

提示：

n == houses.length

1 左边及本身的房子数小于右边的房子数，右移动。右边及本身的房子数小于左边的房子数，左移动。​ → \rightarrow → 稳定状态下，必须= i1 \rightarrow abs(i1-i2)i1=i2,i1=i2,i2+1>=i1→abs(i1−i2)public:int minDistance(vectorm_c = houses.size();sort(houses.begin(), houses.end());vector{int iDis = 0;for (int i = center, j = center; (i = 0) && (j