u**7
发帖数: 200 | 1 find a intersection to build office so that the sum of all employees'
commute distances is minimum.. (the map is represented as a m*n grid, you
are given each employee's coordination, they can only move in up-down and
left-right directions)
这题目除了O(mn)的brute force做法外，还有什么更加高效的吗。
谢谢了 |
g*****g
发帖数: 212 | 2 x mean y mean
【在 u**7 的大作中提到】
: find a intersection to build office so that the sum of all employees'
: commute distances is minimum.. (the map is represented as a m*n grid, you
: are given each employee's coordination, they can only move in up-down and
: left-right directions)
: 这题目除了O(mn)的brute force做法外，还有什么更加高效的吗。
: 谢谢了
|
w*******i
发帖数: 186 | 3 如果是求最小的欧式距离平方和，取中点坐标一定正确，求导可证。不过如果求最小的
曼哈顿距离之和，取中点感觉不够严格啊。。。
【在 g*****g 的大作中提到】
: x mean y mean
|
r****c
发帖数: 2585 | |
h*****k
发帖数: 15 | 5 中位数
★ 发自iPhone App: ChineseWeb 7.8
【在 u**7 的大作中提到】
: find a intersection to build office so that the sum of all employees'
: commute distances is minimum.. (the map is represented as a m*n grid, you
: are given each employee's coordination, they can only move in up-down and
: left-right directions)
: 这题目除了O(mn)的brute force做法外，还有什么更加高效的吗。
: 谢谢了
|
s********i
发帖数: 74 | |
g******n
发帖数: 10 | |
