w******j
发帖数: 185 | 1 2d matrix, each point represents the location of a person, find the meeting
point which would minimize the distance travalled by all of them
到底怎么做？谢谢 |
n***i
发帖数: 777 | 2 this optimal point must be one of the point on the 2d matrix (equally
optimal is possible if not choose one of the point on the 2D matrix)
enumerate all the cases
meeting
【在 w******j 的大作中提到】
: 2d matrix, each point represents the location of a person, find the meeting
: point which would minimize the distance travalled by all of them
: 到底怎么做？谢谢
|
r**h
发帖数: 1288 | 3 没记错的话这一题的解是每个人所在位置的x轴坐标和y轴坐标的median
meeting
【在 w******j 的大作中提到】
: 2d matrix, each point represents the location of a person, find the meeting
: point which would minimize the distance travalled by all of them
: 到底怎么做？谢谢
|
s*w
发帖数: 729 | 4 人走路的距离是 block distance 还是 Euclidean distacne?
meeting
【在 w******j 的大作中提到】
: 2d matrix, each point represents the location of a person, find the meeting
: point which would minimize the distance travalled by all of them
: 到底怎么做？谢谢
|
r**h
发帖数: 1288 | 5 算曼哈顿距离吧？
否则就是重心咯
【在 s*w 的大作中提到】
: 人走路的距离是 block distance 还是 Euclidean distacne?
:
: meeting
|
a*********0
发帖数: 2727 | 6 这题难道不就是找到在x和y方向上距离最远的2个人的坐标取中？
【在 r**h 的大作中提到】
: 算曼哈顿距离吧？
: 否则就是重心咯
|
r*****s
发帖数: 74 | 7 我记得也是这样……
【在 r**h 的大作中提到】
: 没记错的话这一题的解是每个人所在位置的x轴坐标和y轴坐标的median
:
: meeting
|
a*********0
发帖数: 2727 | 8 应该还得考虑人的分布，晕
【在 a*********0 的大作中提到】
: 这题难道不就是找到在x和y方向上距离最远的2个人的坐标取中？
|
n***i
发帖数: 777 | 9 如果一维的话是median，二维的话证明不出
【在 r**h 的大作中提到】
: 没记错的话这一题的解是每个人所在位置的x轴坐标和y轴坐标的median
:
: meeting
|
K********y
发帖数: 47 | 10 我见过的是Manhattan distance。答案的x/y坐标分别是N个点x/y坐标的median。二维
问题可以分离：sum_i(|x-x_i|+|y-y_i|) = sum_i(|x-x_i|) + sum_i(|y-y_i|)。
median的两边各有N/2个人，从median往左（上）走一步，有N/2个人多走一步，N/2个
人少走一步。如果左边人数多于右边，往左挪一步可以减少总步数。当然如果N是偶数
，其实不需要真正的median，可以是最中间两个人之间的任何地方。 |
