algorithm - 放置邮箱的算法，以最小化居民获取邮件的总距离

假设输入被指定为一组建筑物对象，其中每座建筑物都具有一定数量的居民，距离街道的起点有一定距离。

总距离= SUM(距离[i] *＃居民[i])

我在这里发现了两个相似的问题，但它们的要求略有不同:

Minimizing weighted sum:此问题的解决方案找到了跨越所有点的最小路径。在这里，我正在寻找从每个建筑物到邮箱所在位置的总距离的最小总和。

Minimum Total Distance From Locations:它使用2D坐标，更重要的是，该解决方案未考虑每个位置的权重(居民人数)。

在阅读《编程面试元素》(这本非常不错的书，BTW)时，我看到了这个问题，它被列为快速选择算法的一种变体。考虑到中位数是使距离总和最小的点，因此该解决方案似乎涉及快速选择以在O(N)中的街道“中间”位置找到建筑物。

但是我无法弄清楚如何对每座建筑物上的居民进行核算，并且仍然保持解决方案的线性。

最佳答案

我们可以使用增量来确定方向。我会解释我的意思。与选择建筑物之一(即不在两座建筑物之间)的邮箱位置有关:

选择建筑物之一作为枢轴(潜在的邮箱位置)。根据建筑物相对于枢轴的位置对建筑物进行分区。进行分区时，请记录枢纽各侧最近的建筑物，以及(1)枢纽各侧的居民总数，以及(2)f(side, pivot)，代表各建筑物与枢纽的距离之和枢轴乘以该建筑物中的居民人数。

现在我们有:

L pivot R

要确定是否可以对我们的选择进行改进，请尝试我们之前记录的每个最接近的建筑物:

如果我们将选择的一栋建筑物向左移动，结果将如何变化？让我们将最左边的建筑物称为build_l，将最右边的建筑物称为build_r。因此，将我们选择的建筑物向左移动的新结果将是:

左边:

  f(L, pivot)
- distance(build_l, pivot) * num_residents(build_l)

右边:

  f(R, pivot)
  // we saved this earlier
+ total_residents(R) * distance(pivot, build_l)
+ num_residents(pivot) * distance(pivot, build_l)

执行类似的计算，将选择的一栋建筑物向右移动，以查看总建筑物较小的情况。然后选择产生改进的建筑物一侧，并以类似的快速选择方式递归划分它，直到找到最佳结果。另一方面，我们会跟踪居民总数以及到目前为止f的总结果，我们可以在进行更新时使用新添加的内容进行更新。