货仓选址原题

给定在一个一维数轴上的多个点，请找出一个位置，使得这个位置和所有点的距离之和最小。

思路

这样的题目在学习数学数形结合的时候其实就学到了，也就是选择最中间的数。这个结论可以通过调整法证明。

证明

我们假设我们选择的数左边还有 $A$ 个数，右边还有 $B$ 个数。

一共有奇数个数

这个时候，由于我们选的数是最中间的数，也就是第 $\frac{n + 1}{2}$ 个数，所以 $A = B$。这个时候如果我们让我们选的这个数是中位数减一：那么所有左边的 $A$ 个数离这个数的距离都减小了一（我们假设每个数之间的间隔大于等于 $1$），右边的 $B$ 换个数都会加上一，但是注意由于我们现在选的不是中位数了，所以距离总和会而外产生一个 $+1$。由于 $A = B$，$\Delta S = B-A+1 = 1 > 0$，所以选中间的数是最优的。

由于 $A=B$，所以 $+1$ 同理。

一共有偶数个数

这个时候我们假设我们选的数是中间两个数中靠左边的数，也就是第 $\frac{n}{2}$ 个数，所以 $A + 1 = B$。这个时候如果我们把我们选择的数减 $1$，那么同理，$\Delta S = B-A+1=2>0$；如果我们把我们选择的数加 $1$，那么 $\Delta S = A+1-B=0$，也就是我们发现没有变化。

所以我们可以得出，$n$ 为偶数的时候，去最中间两个数之间的任意一个数都一样。

具体计算最小距离和

我们可以通过前缀和的方法，用后一半的元素之和减去前一半的。

圆上货仓选址

可以看题目：USACO 2025 January Contest, Silver Problem 2. Farmer John’s Favorite Operation

区别于原题，这里的点是在一个环上面的，所以比如说这个环的长度为 $60$，$1$ 和 $60$ 的最短距离就是 $1$ 了。

所以，我们采取断环为链的操作，我们往后复制一个

然后，我们枚举每种可能的起始点（复杂度 $O(n)$），然后用前缀和预处理，能实现对于每个起始点都可以 $O(1)$ 计算。