我在 interviewStreet 上在线找到了一个谜题并尝试如下解决:
There is an infinite integer grid at which N people have their houses on. They decide to unite at a common meeting place, which is someone's house. From any given cell, all 8 adjacent cells are reachable in 1 unit of time. eg: (x,y) can be reached from (x-1,y+1) in a single unit of time. Find a common meeting place which minimizes the sum of the travel times of all the persons.
我首先想到的是及时编写一个 n² 复杂度的解决方案,但限制条件是
1<=N<=10^5 and The absolute value of each co-ordinate in the input will be atmost 10^9
因此,我改变了我的第一种方法,不再关注距离和旅行时间的问题,而是将不同的房屋视为具有不同重量的不同物体。我没有计算所有的距离,而是寻找这组物体的重心。
这是我的“解决”函数的代码,vectorToTreat 是一个 lengthX2 表,存储关于网格上的点的所有数据,resul 是打印到标准输出的数字:
long long solve(long long** vectorToTreat, int length){
long long resul = 0;
int i;
long long x=0;
long long y=0;
int tmpCur=-1;
long long tmp=-1;
for(i=0;i<length;i++){
x+=vectorToTreat[i][0];
y+=vectorToTreat[i][1];
}
x=x/length;
y=y/length;
tmp = max(absol(vectorToTreat[0][0]-x),absol(vectorToTreat[0][1]-y));
tmpCur = 0;
for(i=1;i<length;i++){
if(max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y))<tmp){
tmp = max(absol(vectorToTreat[i][0]-x),absol(vectorToTreat[i][1]-y));
tmpCur = i;
}
}
for(i=0;i<length;i++){
if(i!=tmpCur)
resul += max(absol(vectorToTreat[i][0]-vectorToTreat[tmpCur][0]),absol(vectorToTreat[i][1]-vectorToTreat[tmpCur][1]));
}
return resul;
}
现在的问题是我通过了 12 个超过 13 个的官方测试用例,但我没有看到我做错了什么,有什么想法吗? 提前致谢。 AE
最佳答案
这个问题的关键是 centroid of a set of points 的概念.集合地点是距离代表所有房屋的一组点的质心最近的房屋。使用这种方法,您可以在线性时间内解决问题,即 O(N)。我是用 Python 完成的,提交了我的解决方案并通过了所有测试。
但是,构建质心方法不起作用的数据集很容易。这是一个例子:
[(0, 0), (0, 1), (0, 2), (0, 3),
(1, 0), (1, 1), (1, 2), (1, 3),
(2, 0), (2, 1), (2, 2), (2, 3),
(3, 0), (3, 1), (3, 2), (3, 3),
(101, 101)]
最好的解决方案是在 (2, 2) 的房子里会面,成本是 121(您可以通过穷举搜索找到它 - O(N^2))。然而,质心方法给出了不同的结果:
- 质心是 (7, 7)
- 离质心最近的房子是 (3, 3)
- 在 (3, 3) 开会的费用是 132
网站上的测试用例显然是以质心解决方案 OK 的方式塑造的,或者他们可能只是想弄清楚您是否了解质心的概念。
关于c - 所有旅行时间的最小总和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7171011/