p**********e 发帖数: 316 | 1 http://www.mitbbs.com/article_t/JobHunting/32281037.html
一个二维数组代表了城市中的坐标,给定N个人的坐标,求坐标使所有人
走到这个坐标的距离的和最小,只可以横着或者竖着走,不可以斜着走
更一般性的问题是找一个地方建distribution center,如何选址
另一个问题
given an array of strings, 求max len(A)*len(B), A B have no common character
一个貌似很简单的问题,
给定两个array of integers, the same size, 两两配对, 求绝对值之和最小
http://mattcb.blogspot.com/2013/03/minimum-weight-of-two-groups
没看懂解法 | s**x 发帖数: 7506 | 2 第一题好像以前讨论过。
一维的情况, one point, it is the point, 2 points, any point between the
two points should work, 3 points, should be the middle point.
so it should be the median point.
2D, X Y direction should be independent, so it is just to find the median
for all numbers in X Y direction separately. | x*****0 发帖数: 452 | | M***A 发帖数: 5 | 4 顶
最后那题我觉得那个blog给出的答案把问题复杂化了。大概他是想考虑可以重复选某个
数的情况。比如只选b1,出现(a1, b1), (a2, b1), (a3, b1)三个pair。
其实我觉得没必要,只要排序然后计算sum|ai - bi|就可以了。
【在 p**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.mitbbs.com/article_t/JobHunting/32281037.html : 一个二维数组代表了城市中的坐标,给定N个人的坐标,求坐标使所有人 : 走到这个坐标的距离的和最小,只可以横着或者竖着走,不可以斜着走 : 更一般性的问题是找一个地方建distribution center,如何选址 : 另一个问题 : given an array of strings, 求max len(A)*len(B), A B have no common character : 一个貌似很简单的问题, : 给定两个array of integers, the same size, 两两配对, 求绝对值之和最小 : http://mattcb.blogspot.com/2013/03/minimum-weight-of-two-groups : 没看懂解法
| h*****u 发帖数: 109 | 5 我感觉这个是one-to-all shortest path的变形。如果在坐标上有一个点s,距离的和
最小,等同于每个城市到s的shortest distance。
for s in all points
determine the sum of the shortest distances
output the minimum one
算shortest distances时,可以用all-pair shortest paths, such as Floyd-
Warshall | h*****u 发帖数: 109 | 6 A[]={5,3,4};
B[]={1,6,2};
min = 5
3-1, 4-2,5-6
这个是assignment problem的应用。
首先
for i in A
for j in B
compute the abs(i,j)
abs 用作在objective里。然后就是assignment problem.
如何解assignment, 可以看看Kuhn的Hungarian_algorithm
http://en.wikipedia.org/wiki/Hungarian_algorithm | g*****g 发帖数: 212 | 7 blog那个解法貌似是错的。。。
character
【在 p**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : http://www.mitbbs.com/article_t/JobHunting/32281037.html : 一个二维数组代表了城市中的坐标,给定N个人的坐标,求坐标使所有人 : 走到这个坐标的距离的和最小,只可以横着或者竖着走,不可以斜着走 : 更一般性的问题是找一个地方建distribution center,如何选址 : 另一个问题 : given an array of strings, 求max len(A)*len(B), A B have no common character : 一个貌似很简单的问题, : 给定两个array of integers, the same size, 两两配对, 求绝对值之和最小 : http://mattcb.blogspot.com/2013/03/minimum-weight-of-two-groups : 没看懂解法
| h*****u 发帖数: 109 | 8 如果没有障碍物,这题应该不用求shortest path. 可以直接用weighted median, 先是
X, 然后Y. 可以看CLRS order statistics的习题。网上有答案。 | p******e 发帖数: 14 | |
|