题目描述

一条笔直的高速公路上有 $N$ 个村庄，每个村庄都有一个整数位置坐标，不同村庄的坐标不同，现在要在其中的 $P$ 个村庄上建立邮局。

请问如何安排邮局的位置可以使得每个村庄到其最近邮局的距离和最小，输出这个最小值。

输入格式

第一行包含两个整数 $N$ 和 $P$，分别表示村庄数量以及邮局数量。

第二行包含 $N$ 个整数，表示 $N$ 个村庄的位置坐标，坐标均为不超过 $10000$ 的正整数。

输出格式

输出一个整数，表示距离和的最小值。

样例

10 5
1 2 3 6 7 9 11 22 44 50

9

样例解释

输入

$N=10, P=5$ 村庄坐标：$[1, 2, 3, 6, 7, 9, 11, 22, 44, 50]$

要求

选择 $P=5$ 个村庄建立邮局，使得所有村庄到最近邮局的距离之和最小。

分析

这是一个经典的邮局选址问题。

村庄在一条直线上，邮局只能建在村庄上（题目说“在其中的 P 个村庄上建立邮局”）。

我们需要选择 $P$ 个村庄作为邮局，最小化总距离。

预处理

设村庄坐标已经排序（输入已经排序？样例是升序的，但题目没说明，所以我们需要先排序）。

设排序后的坐标为 $x_1 < x_2 < \dots < x_N$。

定义 $cost(i,j)$ 表示在村庄 $i$ 到 $j$ 之间（包括 $i$ 和 $j$）建立一个邮局时，这些村庄到该邮局的最小距离和。

可以证明：当邮局建在区间 $[i,j]$ 的中位数位置（即第 $\lfloor (i+j)/2 \rfloor$ 个村庄）时，距离和最小。

因此，我们可以预处理 $cost(i,j)$：

设邮局建在村庄 $k$（$i \le k \le j$），则距离和 $= \sum_{t=i}^j |x_t - x_k|$。当 $k$ 为中位数时最小。

由于 $i$ 和 $j$ 是索引，中位数索引 $mid = (i+j)/2$ 向下取整。

$cost(i,j) = \sum_{t=i}^j |x_t - x_{mid}|$。

可以通过前缀和快速计算：设 $pref[i] = \sum_{t=1}^i x_t$。

则 $\sum_{t=i}^j |x_t - x_{mid}| = x_{mid} \times (mid-i+1) - (pref[mid] - pref[i-1]) + (pref[j] - pref[mid]) - x_{mid} \times (j-mid)$。

动态规划

设 $dp[i][k]$ 表示在前 $i$ 个村庄中建立 $k$ 个邮局的最小总距离。

转移：考虑最后一个邮局服务的区间 $[j+1, i]$（$j < i$），则

$$dp[i][k] = \min_{0 \le j < i} \{ dp[j][k-1] + cost(j+1, i) \}$$

其中 $dp[0][0] = 0$，其他初始化为无穷大。

答案：$dp[N][P]$。

复杂度：$O(N^2 \times P)$，对于 $N=300, P=30$，$300^2 \times 30 = 2.7 \times 10^6$，可以接受。

样例计算

排序后的坐标已经是升序。

计算 $cost(i,j)$ 示例：

• $cost(1,3)$：区间 $[1,2,3]$，中位数 $x_2=2$，距离和 $=|1-2|+|2-2|+|3-2|=1+0+1=2$。

我们需要计算 $dp[10][5]$。

通过 DP 可以得到最小总距离为 9。

验证一种可能方案： 选择邮局在村庄 2, 6, 9, 10（坐标 2, 7, 22, 50）？不对，需要 5 个邮局。

假设选择邮局在坐标 2, 7, 11, 22, 50：

• 村庄 1（1）最近邮局 2，距离 1
• 村庄 2（2）距离 0
• 村庄 3（3）最近 2，距离 1
• 村庄 4（6）最近 7，距离 1
• 村庄 5（7）距离 0
• 村庄 6（9）最近 7，距离 2
• 村庄 7（11）距离 0
• 村庄 8（22）距离 0
• 村庄 9（44）最近 50，距离 6
• 村庄 10（50）距离 0 总距离 = 1+0+1+1+0+2+0+0+6+0 = 11，大于 9。

所以有更优方案。

可能选择邮局在坐标 2, 7, 11, 22, 44：

• 1→2:1
• 2→2:0
• 3→2:1
• 4→7:1
• 5→7:0
• 6→7:2
• 7→11:0
• 8→22:0
• 9→44:0
• 10→44:6 总距离 = 1+0+1+1+0+2+0+0+0+6 = 11。

选择邮局在 3, 7, 11, 22, 44：

• 1→3:2
• 2→3:1
• 3→3:0
• 4→7:1
• 5→7:0
• 6→7:2
• 7→11:0
• 8→22:0
• 9→44:0
• 10→44:6 总距离 = 2+1+0+1+0+2+0+0+0+6=12。

可见 9 更优。

通过 DP 可以得到最优方案。

数据范围

• $1 \le N \le 300$
• $1 \le P \le 30$

算法总结

1. 读入 $N, P$ 和村庄坐标数组 $x$。
2. 对 $x$ 排序。
3. 预处理前缀和 $pref$。
4. 预处理 $cost(i,j)$ 数组（$1 \le i \le j \le N$）。
5. 动态规划计算 $dp[i][k]$。
6. 输出 $dp[N][P]$。

动态规划优化

由于 $cost(i,j)$ 满足四边形不等式，可以使用决策单调性优化将复杂度降为 $O(N \times P)$。但本题 $N$ 较小，直接 $O(N^2 P)$ 即可。

注意事项

• 邮局必须建在村庄上。
• 村庄坐标需要排序。
• $dp$ 数组初始化 $dp[0][0]=0$，其他为无穷大。
• 枚举 $j$ 时，$j$ 可以从 $k-1$ 开始（因为前 $i$ 个村庄建 $k$ 个邮局，至少需要 $k$ 个村庄）。

复杂度

• 预处理 $cost$：$O(N^2)$。
• DP：$O(N^2 \times P)$。
• 总计算量约 $300^2 \times 30 = 2.7 \times 10^6$，很快。