c - 所有旅行时间的最小总和

Question

我在 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

Answer 1

这个问题的关键是 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 的方式塑造的，或者他们可能只是想弄清楚您是否了解质心的概念。