一道看似简单的数学题求解。

[xqdoo00o]

假设有 n 个数值 X1 到 Xk，如何求得一个数，使得每个数值减去该数的绝对值之和 最小。即求使得下面表达式最小的？值。

该表达式等价于

[shyrock]

最小生成树？

[xqdoo00o]

脑算了下，感觉应该是 中位数，但是不知道怎么证明😂

[Hypn0s]

不就是 X1 到 Xk 的平均值吗

[eccstartup]

奇数个为中位数，偶数个为中间两个值构成闭区间内的任意一个点。

[xqdoo00o]

@Hypn0s 并不是，反例：1，9，11。平均数 7，但 9 是对的。

[xqdoo00o]

@eccstartup 嗯，我也是认为，就是不知道该怎么证明

[yoohwzy]

记该数为 x，把第二个式子展开求导即可， 结果如三楼所说

[Hypn0s]

@xqdoo00o #5 emmmmmmmmm，想了下是欠考虑了，应该是中位数，归纳法可证

[icct]

两问题不等价

[xqdoo00o]

@icct 感觉应该等价啊，求解。

[wwg1994]

有 2 个数，x、y，y>=x
求 1 数 z 使 |x-z| + |y-z| 最小
显然 只要 x<=z<=y 即可

映射到这个题目，求 z
将原数列排序
循环弹出数列首尾，
当数列长度=2 或者 1 时结束循环，
长度=2 时，z 的取值范围在这 2 个元素之间
长度=1 时，z 的值等于这个元素

[yoohwzy]

这两个式子不等价， 展开求导只针对第二个式子

[youngjjj]

把点画到数轴上，可以看出只能选中位数上那个点才能使距离之和最短，选其他点都会多出一段长度。

[yoohwzy]

你把第一个式子平方之后就会发现， 第二个式子只是平方结果的一部分

[wwg1994]

弹出首尾的意思是，每次弹出 1 对数
z 的取值应该在这对数的区间内

[salinapper]

@xqdoo00o #10 明显不等价啊，平方之后，大数的影响增大了。
比如 |100| == |-50| + |50|
然而 100^2 == 10000 > 5000 == (-50)^2 + (50)^2

[mixz]

把点排列到数轴上，然后把点拆成很多组，如果是偶数，则两个为一组，如 3 5 7 9，则拆成两组，{3，9}，{5，7}。如果是奇数，如 1 3 5 7 9，则拆成{1，9}，{3，7}，{5}。现在只要找到一个点，使得这个点到每个组的距离为最短（组的距离即为到两点的距离之和），那么这个点就是所求的点，如到{3，9}距离最短的点，只需要在 3 和 9 的中间即可，依此类推，易求证。

[xqdoo00o]

@salinapper 哦，是，忘了

[sosilver]

https://en.wikipedia.org/wiki/Geometric_median

[Michaelssss]

画一张图，x 轴为 k，y 轴为 Xk 你说的就是图像上一根平行 x 轴的线，这根线是让所有点的距离最小。。那么显然，这根线应该穿过这堆点的中间