my cnblog

基本问题（均分纸牌）

有 $n$ 个小朋友坐成一排，每人有 $a_i$ 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 $1$，求使所有人获得均等糖果的最小代价。

先抛出式子：
$$设c_i = \lvert{ \sum_{j = 1}^i{a_j} - i * avg \vert} \ , \ W = \sum_{i = 1}^n{c_i}$$

证明：

首先第$i$个小孩一定是向第$i + 1$个小孩那里索取或传递糖果，设交换值为 $p_i$。

目标是使所有人手中的糖果数量为平均值($avg$)，那么经过$n - 1$轮交换后，得出式子：
$$a_1 - p_1 = avg$$
$$a_2 + p_1 - p_2 = avg$$
$$a_3 + p_2 - p_3 = avg$$
$$……$$
$$a_n + p_{n - 1} = avg$$

以第$i$项为例，将$p_i$移到等式左边，其他移到等式右边。
$$p_i = p_{i - 1} + a_i - avg$$

拆开$p_{i - 1}$得（这一步跳得大一点）：
$$p_i = \sum_{j = 1}^i{a_j} - i * avg$$

总代价就是所有交换的数量和（注意一次只能交换一）：
$$W = \sum_{i = 1}^n{|p_i|}$$

证毕。

环形纸牌均分（糖果传递）

有 $n$ 个小朋友坐成一圈，每人有 $a_i$个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 $1$，求使所有人获得均等糖果的最小代价。

与纸牌均分问题相比，变化的是首项和末项。

所有变量的意义和上一个问题相同。

首项：$a_1 + p_n - p_1 = avg$
中间项：$a_i + p_{i - 1} - p_i = avg$
末项：$a_n + p_{n - 1} - p_n = avg$

目标还是所有交换值（$p_i$）之和。

这里需要一个技巧：将所有的$p_1$作为一个单独的变量。

接下来的 $p_2 \ 到 \ p_n$ 可以表示为：
$$p_2 = a_2 - avg + p_1$$
$$p_3 = (a_2 - avg) + (a_3 - avg) + p_1$$
$$……$$

设： $$c_i = \sum_{j = 2}^i{a_j} - i * avg \ , \ c1 = 0$$

则 $p_1 = c_1 + p_1 \ , \ p_2 = c_2 + p_1 \ , ……$
答案即： $$W = \sum_{i = 1}^n{|c_i + p_1|}$$

证毕。问题这个 $p_1$ 是多少呢？

这个式子可以继续变化： $$W = \sum_{i = 1}^n{|c_i - ( -p_1 )|}$$

这样就是标准的货仓选址问题了。
货舱选址中的最佳位置就是数轴上的点集位置中的中位数。

第一个小朋友可以传递的糖果数是任意整数个，只要使$p_1$取所有$c_i$的中位数就可以让传递代价最小。

所以解决的方案就是先预处理出所有的 $c_i$ ，然后取中位数，遍历一遍 $c$ 计算结果。

总结

所有有关均值变换和选址问题且距离最短的，都可以在这个规律上变换式子解决问题。

重要的是能够灵活的运用中位数。

例题

供参考的例题：

均分纸牌
糖果传递
货舱选址
七夕祭