Best Meeting Point
给一个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
Read full article from Best Meeting Point | 书脊
No comments:
Post a Comment