这里的问题是找到所有整数点的集合，它给出了给定点集的所有曼哈顿距离的最小总和！
例如：
让我们有一组给定的点 { P1, P2, P3...Pn }
基本问题是找到一个点 X，该点在距点 { P1, P2, P3...Pn } 的所有距离上具有最小总和。
即 |P1-X| + |P2-X| + .... + |Pn-X| = D，其中 D 将是所有 X 中的最小值。
更进一步，满足上述条件的 X 值可以有多个。即，可能有多个 X 给出相同的值 D。因此，我们需要找到所有这样的 X。
任何人都可以想到的一种基本方法是找到输入的中位数，然后暴力破解中提到的坐标这个帖子 https://stackoverflow.com/questions/10402087/algorithm-for-minimum-manhattan-distance
但这种方法的问题是：如果中位数给出两个相距甚远的值，那么我们最终会暴力破解所有在给定时间内永远不会运行的点。
那么，是否有任何其他方法即使在点相距很远的情况下也能给出结果（其中中位数给出的范围约为 10^9）。
您可以单独考虑 X 和 Y，因为它们彼此独立地增加距离。这将问题简化为在给定一条线上的 n 个点的情况下寻找到其他点的距离和最小的点。这很简单：两个中位数（含）之间的任何点都满足这一点。
Proof：如果点数为偶数，则有两个中位数。两个中位数之间的点将有 n/2 个点向左，n/2 个点向右，以及到 S 的这些点的总距离和。
如果我们向左移动一点，S 将上升 n/2（因为我们正在远离最右边的点）并减少了 n/2（因为我们正在向最左边的点移动），所以整体 S 保持不变。在我们到达最左边的中点之前，这一点一直成立。当我们将最左侧中点向左移动一位时，现在向右有 (n/2 + 1) 个点，向左有 (n/2 - 1) 个点，因此 S 增加了 2。继续向左只会进一步增加 S。
按照同样的逻辑，最右侧中位数右侧的所有点也具有较高的 S。
如果点数为奇数，则只有一个中位数。使用与上面相同的逻辑，我们可以证明它具有最低的 S 值。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
