货仓选址问题题解 & 拓展

货仓选址原题

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

思路

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

证明

我们假设我们选择的数左边还有 $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)$ 计算。

本文链接:https://ztrztr.top/archives/984
版权声明:本文 《货仓选址问题题解 & 拓展》 为 ztrztr 原创。著作权归作者所有。
转载说明:联系作者或者评论区留言获得转载授权,并注明转载地址。
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇