好像是某道CF问题的变形, 记一下.

题目描述

有若干的排列在一条直线上的点\(p_i\), 每个点上有\(a_i\)个人, 找出一个点, 使得所有人移动带这个人的位置上的总距离最小.

结论. 从左到右累加人数, 寻找刚刚过半的人数.
证明. (扰动法) 若\(\sum_{i=1}^{x-1}<\sum a_i /2\), \(\sum_{i=1}^{x}\geq\sum a_i /2\), 这个\(x\)就是要求的. 假设所有人集合到\(p_x\)走的总距离是\(A\), 记作\(D(x)\).

考虑$$D(x-1)=\sum_{i=1}^{x-1}a_i\times|p_x-p_{x-1}| + \sum_{i=x}^{n}a_i\times|p_x-p_{x-1}|.$$

由于左边的人数小于一半, 这样调整之后的人数只会增加. 所以会更劣.

同理可证右半边.

拓展.

如果每个人还有一个等待时间.
结论. 把每个人拆成两个, 一个左边, 一个右边, 也是正确答案.