解题思路
曼哈顿距离可以把横、纵两个方向拆开，本题等价于分别在数轴上选 P 和 Q，使加权一维距离和最小，再用加权中位数求出这两个坐标。
- 工厂落在 (P,Q) 时，总路程为 ∑wi∣ai−P∣+∑wi∣bi−Q∣。前一项只与 P 有关，后一项只与 Q 有关，可以分开最小化。
- 一维上，点 zi 带权 wi，使 ∑wi∣zi−x∣ 最小的 x 就是加权中位数：把点按坐标排序后从左往右累加权重，第一次让前缀权重至少达到总权重一半的那个坐标即可。总权重为偶数时，两个中间位置之间的任意点代价相同，取先达到一半的那个即可。
- 对横坐标序列 (ai,wi) 求加权中位数得到 P，对纵坐标序列 (bi,wi) 同样得到 Q。
- 把 (P,Q) 代回原式，累加每个居民区的加权曼哈顿距离。坐标与人数都较大，求和时用 64 位整数。
