java - 设计一个有效的算法来找到最小化平均距离的邮局位置

Question

令 x1< x2 < 。 . . < xn 是实数，表示沿着一条直路的 n 个村庄的坐标。需要在其中一个村庄中 build 一个邮局。a) 设计一个有效的算法来找到邮局位置，最小化村庄和邮局之间的平均距离。

我已经写了这个算法，谁能检查它是否正确？

Algorithm PostOffice(P)

    m <- (x1+xn) / 2
    i <- 1
    while xi < m do
        i <- i+1
    if xi - x1 < xn - xi-1
        return xi
    else return xi-1

Answer 1

如果我们必须在每次访问时返回邮局，则可以按照以下方法找到最佳位置。如果有奇数个点，则最佳位置是排序顺序中的中间点。否则，按输入排序顺序位于中间的两点之间的所有点都是最优的。这个问题称为 1-中值问题。

PS:我认为这不是问题所在，但如果 postman 从邮局出发，经过城市并最终回到邮局，则最小点和最大点之间的每个点都是最佳的。成本等于 2*(X_max - X_min)