给一个2d的grid, 上边有1也有0. 让你找一个点使得所有点到这点的Manhattan Distance 的合为最小. 这题考点很多: 首先,Manhattan Distance 的合为 sum(distance(p1, p2)) = sum(|p2.x – p1.x| + |p2.y – p1.y|)= sum(|p2.x – p1.x|)+sum(|p2.y – p1.y|). 也就是说, 可以分别计算x和y的合, 然后加起来. 其次, 我们需要把2d的grid变成1d, 这里的窍门是, 我们可以证明, 所求的点, 就在其中某点的x或者y的坐标轴上. 所以, 而这点, 必然是1d下的median. http://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations Suppose we have a set S of real numbers that ∑s∈S|s−x|is minimal if x is equal to themedian. 所以, 我们需要count一下x轴上有多少个1的投影, 和y轴上有多少个1的投影. […]