algorithm - 与所有其他给定点的曼哈顿距离最小的所有点[优化]

Question

这里的问题是找到所有整数点的集合，它给出从给定点集合到所有曼哈顿距离的最小总和!

例如:

让我们有一组给定的点 { P1, P2, P3...Pn }

基本问题是找到一个点 X，它在距点 { P1, P2, P3 ... Pn } 的所有距离上具有最小总和。

即|P1-X| + |P2-X| + .... + |Pn-X| = D，其中 D 将是所有 X 中的最小值。

更进一步，满足上述条件的X值可以有不止一个。即可能有多个 X 给出相同的值 D。因此，我们需要找到所有这样的 X。

任何人都可以想到的一种基本方法是找到输入的中位数，然后暴力计算 this post 中提到的坐标。

但这种方法的问题是:如果中位数给出两个相差很大的值，那么我们最终会强制所有在给定时间内永远不会运行的点。

那么，有没有其他方法可以给出结果，即使点相距很远(其中中位数给出的范围约为 10^9)。

Answer 1

您可以分别考虑 X 和 Y，因为它们相互独立地增加了距离。这将问题简化为在给定直线上的 n 个点的情况下，找到与其他点的距离总和最小的点。这很简单:两个中位数(含)之间的任何点都满足这一点。

---

证明:如果我们有偶数个点，就会有两个中位数。两个中位数之间的点将有 n/2 个点向左和 n/2 个点向右，以及到 S 的这些点的距离总和。

如果我们将它向左移动一个点，S 将上升 n/2 (因为我们正在远离最右边的点) 并下降 n/2 (因为我们正在向最左边的点移动)，所以整体 S 保持不变。在我们到达最左边的中点之前，这种情况一直成立。当我们将最左边的中点向左移动一个时，我们现在有 (n/2 + 1) 个点向右，(n/2 - 1) 个点向左，所以 S 增加了两个。继续向左只会进一步增加 S。
按照同样的逻辑，最右边的中位数右边的所有点也有更高的 S。

如果我们有奇数个点，则只有一个中位数。使用与上述相同的逻辑，我们可以证明它具有最低的 S 值。