工作8年没涨工资，面了一家涨薪 50%。和领导说要是能涨薪 30%就留下，结果领导说:就你?涨5%都多了。。

这题挺有意思的，问题大致是这样的：给你一个排好序的房屋数组，里面存着每栋房子的位置，现在要放置 k 个邮筒，求所有房屋到最近邮筒的最小总距离。

说白了，就是让大家少走冤枉路，毕竟谁也不想拿个快递还得翻山越岭。

思路

看到“最小总距离”这几个字，我的第一反应就是动态规划（Dynamic Programming, DP）或者贪心算法。😏但这题如果用贪心做，容易掉坑里，比如想当然地均匀放置邮筒，结果可能并不是最优解。所以 DP 才是正解。

核心思想：

1. 先计算出 房屋 i 到 j 之间如果放一个邮筒时的最优距离。

2. 设 dp[i][j] 表示 前 j 栋房子放 i 个邮筒的最小距离。

3. 状态转移方程就变成了：

   dp[i][j] = min(dp[i-1][p] + cost[p+1][j])   // p 表示上一个邮筒的位置
   

   其中 cost[p+1][j] 是 p+1 到 j 之间放一个邮筒时的最优距离，可以用中位数来算。

代码

import java.util.Arrays;
public class PostOfficePlacement {
    public int minMailboxDistance(int[] houses, int k) {
        int n = houses.length;
        Arrays.sort(houses); // 确保房屋位置是有序的
                // 预计算 cost[i][j]，即 i 到 j 放一个邮筒的最小距离
        int[][] cost = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int median = houses[(i + j) / 2]; // 取中位数位置
                for (int x = i; x <= j; x++) {
                    cost[i][j] += Math.abs(houses[x] - median);
                }
            }
        }
                // DP 数组
        int[][] dp = new int[k + 1][n];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
                // 只有一个邮筒的情况
        for (int j = 0; j < n; j++) {
            dp[1][j] = cost[0][j];
        }
        // 状态转移
        for (int i = 2; i <= k; i++) { // i 是邮筒数
            for (int j = 0; j < n; j++) { // j 是房屋位置
                for (int p = 0; p < j; p++) { // p 是上一个邮筒的结束位置
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][p] + cost[p + 1][j]);
                }
            }
        }
        return dp[k][n - 1];
    }
    public static void main(String[] args) {
        PostOfficePlacement solver = new PostOfficePlacement();
        int[] houses = {1, 4, 8, 10, 20};
        int k = 3;
        System.out.println(solver.minMailboxDistance(houses, k)); // 5
    }
}

为什么要用中位数？

因为 中位数可以让绝对距离之和最小。这其实是数学上的一个结论，比如 1, 4, 8, 10 这几个数，你要在它们之间放一个点，让所有点到这个点的距离最小，选 8 这个中位数肯定比选 1 或 10 好。

这个 cost 预计算 的操作，把原本的 O(n²) 计算降到了 O(1)，加速了 DP 计算。

时间复杂度

• 预计算 cost[i][j] 需要 **O(n²)**。
• DP 计算 dp[i][j]，每次枚举 p，总复杂度 **O(k * n²)**。
• 所以 **总时间复杂度是 O(n² + k * n²) = O(k * n²)**，可接受。

小结

这题的坑主要有：

1. 不能均匀分配邮筒，有时候集中投放更优。
2. 计算房屋到邮筒的最小距离要用中位数，否则会翻车。
3. **DP 转移状态是 O(k * n²)**，但别担心，Python 会炸，Java 扛得住。

这题有点像让老板决定在哪里开便利店，开多了成本高，开少了员工（房屋）抱怨太远，开在最优位置就可以减少跑路距离。不说了，我要去楼下便利店买瓶快乐水压压惊了。