假设输入指定为建筑物的数组，其中每个建筑物都有许多居民从街道开始的距离。
总距离= sum(距离[i] *＃residents [i](
我在这里发现了两个相似的问题，但要求略有不同：
-
最小化加权总和：该问题的解决方案找到了越过所有点的最小路径。在这里，我正在寻找从每个建筑物到邮箱所在地的总距离的最小总和。
-
距位置的最小总距离：它使用2D坐标，更重要的是，该解决方案不考虑每个位置上的权重(居民数量(。
我在阅读编程访谈的元素(非常好的书，顺便说一句(时看到了这个问题，这被列为QuickSelect算法的变体。考虑到中值是最小化距离之和的点，似乎解决方案将涉及快速选择以在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)
执行类似的计算，以将选择的一栋建筑物移至右侧，以查看哪个产生较小的总数。然后选择建筑物的侧面，从而产生改进并以类似的QuickSelect方式递归分区，直到找到最佳结果为止。另一方面，我们跟踪居民总数，以及到目前为止f的总成绩，我们可以在GO时使用新的添加。
我会以以下方式解决它(下面的伪代码(。
从左到右传递阵列，并计算所有居民将邮箱放在房屋中的成本J＆lt; = i。
# When we place mailbox at building i, all its residents contribute 0 to the total cost.
current_number_of_residents += residents_at_building[i-1]
# For each resident we've seen so far, the cost is increased by building_location[i] - building_location[i-1]
distance_delta = building_location[i] - building_location[i-1]
C_left[i] = C_left[i-1] + distance_delta * current_number_of_residents
然后，我们以类似的方式处理阵列左右。现在，我们可以通过检查最低总和来找到最佳位置：
min_total_distance = min(min_total_distance, C_left[i] + C_right[i])
时间复杂性为o(n(，因为我们在数组上进行了3次通过。空间复杂性是O(n(保留C_left和C_RIGRT数组。
QuickSelect算法复杂性(由 @גלעד-ברקן提出(也平均是O(n(，但在最坏情况下可以是O(n^2(。因此，我看不到这种方法的好处，而不是我的建议。欢迎任何评论。