版花在么，这只小狗太好看了。 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Living

版花在么，这只小狗太好看了。

版花在么，这只小狗太好看了。# Living

p*e2013-03-27 07:03

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*l2013-03-27 07:03

2 楼

400000 cars

d*02013-03-27 07:03

3 楼

太浩湖踏雪

s*x2013-03-27 07:03

4 楼

第一题好像以前讨论过。
一维的情况， 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.

b*c2013-03-27 07:03

5 楼

没有艾迪威风

【在 d**********0 的大作中提到】

: 太浩湖踏雪

x*02013-03-27 07:03

6 楼

d*02013-03-27 07:03

7 楼

俺要的就是小可爱。。//Brush....

【在 b*******c 的大作中提到】

: 没有艾迪威风

M*A2013-03-27 07:03

8 楼

顶
最后那题我觉得那个blog给出的答案把问题复杂化了。大概他是想考虑可以重复选某个
数的情况。比如只选b1，出现(a1, b1), (a2, b1), (a3, b1)三个pair。
其实我觉得没必要，只要排序然后计算sum|ai - bi|就可以了。

【在 p**********e 的大作中提到】

: 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
: 没看懂解法

p*g2013-03-27 07:03

9 楼

和你的头像一样，太娘了

h*u2013-03-27 07:03

10 楼

我感觉这个是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

u*q2013-03-27 07:03

11 楼

这是艾迪的lunch，no？

h*u2013-03-27 07:03

12 楼

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

p*g2013-03-27 07:03

13 楼

帅哥，你的头像太迷人了

【在 u****q 的大作中提到】

: 这是艾迪的lunch，no？