题解：P4016 负载平衡问题

· · 题解

设第 i 个人向左边转移了 K_i 件物品（第一个人向第 n 个转移）（负数代表往右转移），A 是原数组，x_A 表示 A 的平均数，可以列出如下方程，

A_1 - K_1 + K_2 = x_A \\ A_2 - K_2 + K_3 = x_A \\ \dots \\ A_{n-1} - K_{n-1} + K_n = x_A \end{cases}

移项，得，

K_2 = K_1 + x_A - A_1 \\ K_3 = K_2 + x_A - A_2 \\ \dots \\ K_{n} = K_{n-1} + x_A - A_{n-1} \end{cases}

通过代入，将每一项都用 K_1 表示出来，得到，

$K_{i} = K_1 - \sum_{j=1}^{i-1}(A_j-x_A)$， 由于最终答案 $ans = \min\{\sum_{i=1}^{n}|K_i|\}$， 设 $B_i = \sum_{j=1}^{i-1}(A_j-x_A)$， 为了使答案最小，我们取 $K_1$ 为 $B$ 从 $1$ 到 $n$ 的中位数即可。