如何在数轴上最优放置两个点以最小化到给定点集的总距离

核心思路 #

要最小化所有给定点到两个新增点的总距离，核心是将排序后的点集拆分为两个连续子集，每个子集单独选择能使内部总距离最小的点（即子集的中位数或中位数区间内的任意点），再找到总距离最小的拆分方式。

具体步骤 #

1. 排序点集
   首先将所有给定的数轴点按从小到大排序，这是后续操作的基础，时间复杂度为O(n log n)。
   示例输入排序后为：[1, 2, 5, 6]

2. 预处理前缀和数组
   构建前缀和数组，用于快速计算任意子集的最小总距离，避免重复遍历计算。假设排序后的点数组为x[0...n-1]，前缀和数组sum满足sum[0] = 0，sum[i] = x[0] + x[1] + ... + x[i-1]。
   对于任意子集x[l...r]（索引从0开始），其最小总距离可通过公式计算：

   • 子集大小k = r - l + 1
   • 中位数索引m = l + (k-1) // 2
   • 总距离 = x[m]*(m - l + 1) - (sum[m+1] - sum[l]) + (sum[r+1] - sum[m+1]) - x[m]*(r - m)
     这个公式的本质是计算子集内所有点到中位数的距离之和，这是该子集能达到的最小总距离。

3. 遍历所有可能的拆分方式
   将排序后的点集拆分为前k个点和后n-k个点（k的取值范围是1 ≤ k ≤ n-1，保证两组都不为空），对每个拆分计算两组的最小总距离之和，记录总距离最小的拆分方案。
   示例中的拆分情况：

   • k=1：前1个点[1]总距离0，后3个点[2,5,6]总距离4，总和4
   • k=2：前2个点[1,2]总距离1，后2个点[5,6]总距离1，总和2（最优）
   • k=3：前3个点[1,2,5]总距离4，后1个点[6]总距离0，总和4

4. 确定两个最优放置点
   找到总距离最小的拆分后，从两个子集中各选一个能使内部总距离最小的点即可——可以是子集的中位数，也可以是中位数区间内的任意点（比如示例中选x₁=1、x₂=6，或x₁=2、x₂=5，总距离都是2）。

关键结论 #

为什么拆分必须是连续的？因为如果拆分后子集不连续（比如把2分到5,6组，5分到1,2组），调整为连续拆分后总距离一定会更小——排序后的点中，左边的点和左边子集的点距离更近，右边的点和右边子集的点距离更近，交叉分配只会增加总距离。

内容的提问来源于stack exchange，提问作者ICTOAUN