ztrztr 的博客 - 技巧
type: channel
link: https://typecho.ztrztr.top/tag/e6-8a-80-e5-b7-a7/
items: 货仓选址问题题解 & 拓展

货仓选址问题题解 & 拓展
type: item
date: 2025-07-08T02:46:13+08:00
description: 货仓选址原题给定在一个一维数轴上的多个点，请找出一个位置，使得这个位置和所有点的距离之和最小。思路这样的题目在学习数学数形结合的时候其实就学到了，也就是选择最中间的数。这个结论可以通过调整法证明。证明我们假设我们选择的数左边还有 $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)$ 计算。