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

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

总距离= SUM（距离[i] *＃居民[i]）

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

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

到位置的最小总距离：它使用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到目前为止的总结果，我们可以在进行更新时使用新的补充信息进行更新。