所有旅行时间的最小总和

Question

我在interviewStreet网上找到了一个谜题,并尝试按如下方式解决:

有一个无限的整数网格,N人有他们的房子.他们决定团结在一个共同的聚会场所,这是一个人的家.从任何给定的小区,所有8个相邻小区在1个单位时间内可达.例如:(x,y)可以在一个单位时间内从(x-1,y + 1)到达.找到一个共同的聚会场所,最大限度地减少所有人的旅行时间总和.

我首先想到的是及时编写n²复杂度的解决方案,但约束条件是

1 <= N <= 10 ^ 5并且输入中每个坐标的绝对值将至多为10 ^ 9

所以,我改变了我的第一种方法,而不是考虑距离和旅行时间的问题,我把不同的房子看作不同的身体,不同的重量.而不是计算所有距离,我寻找这组物体的重心.

这是我的"求解"函数的代码,vectorToTreat是一个lengthX2表,存储有关网格上各点的所有数据,结果是打印到stdout的数字:

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

这个问题的关键是一组点的质心概念.会议地点是代表所有房屋的一组点的质心最近的房子.使用这种方法,您可以在线性时间内解决问题,即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

网站上的测试用例显然是以质心解决方案正常的方式塑造的,或者他们只是想知道你是否知道质心的概念.

Answer 2

我没有阅读您的代码,但请考虑以下示例:

• 2个人住在(0,0)
• 1个人住在(2,0)
• 4个人住在(3,0)

重心位于(2,0),总行程时间最短为8,但最佳解决方案为(3,0),总行程时间最短为7.

Answer 3

您好，感谢您的回答和评论，它们非常有帮助。我最终放弃了使用重心的算法，当我在上面运行一些样本时，我注意到当房屋聚集在不同的村庄且它们之间的距离不同时，该算法不起作用。如果我们考虑@Rostor上面提到的例子：

(0,0)、(1,0)、(2000,0)、(3000,0)、(3001,0)、(3002, 0)、(3003, 0)

使用重心的算法回答第三宫是解决方案，但正确答案是第四宫。在此类问题中使用的正确概念是中位数，并将其适应所需的维度。这是一篇关于几何中位数的精彩文章，希望对您有所帮助。