放置邮箱以最小化居民获取邮件的总距离的算法
Algorithm to place a mailbox to minimize the total distance that the residents travel to get their mail
假设输入被指定为一个建筑对象数组，其中每个建筑都有一些居民及其与街道起点的距离。
总距离 = SUM(distance[i] * #residents[i])
我在这里发现了两个相似但要求略有不同的问题：
Minimizing weighted sum：这道题的解求的是穿过所有点的最小路径。在这里，我正在寻找从每个建筑物到邮箱所在位置的总距离的最小总和。
Minimum Total Distance From Locations：它使用二维坐标，更重要的是，该解决方案没有考虑每个位置的权重（居民数量）。
我在阅读 Elements of Programming Interviews（非常好的书，BTW）时看到了这个问题，它被列为 quickselect 算法的变体。考虑到中位数是距离总和最小的点，看起来解决方案将涉及快速选择以在 O(N) 中找到街道 "median" 位置的建筑物。
但我无法弄清楚如何计算每栋楼的居民并仍然保持线性的解决方案。
我们可以使用增量来确定方向。我会解释我的意思。因为它涉及在其中一栋建筑物（即不在两栋建筑物之间）选择邮箱位置：
选择其中一栋建筑作为支点（可能的邮箱位置）。根据建筑物相对于枢轴的位置对建筑物进行分区。分区时，记录枢轴每侧最近的建筑物，以及 (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 到目前为止的总结果，我们可以随时更新这些结果。
我会用以下方式解决它（下面的伪代码）。
从左到右传递数组并计算所有居民 j <= i 将邮箱放入房屋 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
然后我们以类似的方式处理数组 right-to-left。
现在我们可以通过检查最小和来找到最佳位置：
min_total_distance = min(min_total_distance, C_left[i] + C_right[i])
时间复杂度为 O(n)，因为我们对数组进行了 3 次传递。 Space 保留 C_left 和 C_right 数组的复杂度为 O(n)。
Quickselect 算法的复杂度（由@גלעד-ברקן 建议）平均也是 O(n)，但在最坏的情况下可以是 O(n^2)。所以我看不出这种方法比我建议的方法有什么好处。欢迎任何评论。
假设输入被指定为一个建筑对象数组，其中每个建筑都有一些居民及其与街道起点的距离。
总距离 = SUM(distance[i] * #residents[i])
我在这里发现了两个相似但要求略有不同的问题：
Minimizing weighted sum：这道题的解求的是穿过所有点的最小路径。在这里，我正在寻找从每个建筑物到邮箱所在位置的总距离的最小总和。
Minimum Total Distance From Locations：它使用二维坐标，更重要的是，该解决方案没有考虑每个位置的权重（居民数量）。
我在阅读 Elements of Programming Interviews（非常好的书，BTW）时看到了这个问题，它被列为 quickselect 算法的变体。考虑到中位数是距离总和最小的点，看起来解决方案将涉及快速选择以在 O(N) 中找到街道 "median" 位置的建筑物。
但我无法弄清楚如何计算每栋楼的居民并仍然保持线性的解决方案。
我们可以使用增量来确定方向。我会解释我的意思。因为它涉及在其中一栋建筑物（即不在两栋建筑物之间）选择邮箱位置：
选择其中一栋建筑作为支点（可能的邮箱位置）。根据建筑物相对于枢轴的位置对建筑物进行分区。分区时，记录枢轴每侧最近的建筑物，以及 (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 到目前为止的总结果，我们可以随时更新这些结果。
我会用以下方式解决它（下面的伪代码）。
从左到右传递数组并计算所有居民 j <= i 将邮箱放入房屋 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
然后我们以类似的方式处理数组 right-to-left。 现在我们可以通过检查最小和来找到最佳位置：
min_total_distance = min(min_total_distance, C_left[i] + C_right[i])
时间复杂度为 O(n)，因为我们对数组进行了 3 次传递。 Space 保留 C_left 和 C_right 数组的复杂度为 O(n)。
Quickselect 算法的复杂度（由@גלעד-ברקן 建议）平均也是 O(n)，但在最坏的情况下可以是 O(n^2)。所以我看不出这种方法比我建议的方法有什么好处。欢迎任何评论。