均分纸牌详解

aimoai / 2024-09-26 / 原文

引入

有 $n$ 个位置，每个位置上有若干张纸牌，每次可以将某个位置的纸牌移向相邻位置，求所有位置纸牌数量相等需要的最少移动次数。

具体还分一次可以移动多张纸牌和一次只能移动一张纸牌两种情况。

线形

位置 $1$ 只和位置 $2$ 相邻，位置 $n$ 只和位置 $n-1$ 相邻，其余位置 $i$ 和位置 $i-1,i+1$ 相邻。

令 $\overline s$ 表示纸牌平均数量，$a_i$ 表示位置 $i$ 初始的纸牌数量。考虑每个位置 $m$：

如果 $\sum\limits_{i=1}^m a_i<m\times\overline s$，那么必然需要从 $m+1$ 向 $m$ 移 $m\times\overline s-\sum\limits_{i=1}^m a_i$ 张纸牌。
如果 $\sum\limits_{i=1}^m a_i>m\times\overline s$，那么必然需要从 $m$ 向 $m+1$ 移 $\left(\sum\limits_{i=1}^m a_i\right)-m\times\overline s$ 张纸牌。
如果 $\sum\limits_{i=1}^m a_i=m\times\overline s$，那么 $m$ 与 $m+1$ 之间不需要移动纸牌。

对于一次可以移动多张纸牌的情况，计算前两种情况的数量即可；对于一次只能移动一张的情况，计算前两种情况纸牌的移动总量即可。

环形

位置 $1$ 和位置 $n,2$ 相邻，位置 $n$ 和位置 $n-1,1$ 相邻，其余位置 $i$ 和位置 $i-1,i+1$ 相邻。

对于一次可以移动多张纸牌的情况，先每个位置减去 $\overline s$，然后枚举每个位置破环成链计算前缀和为 $0$ 的数量。

对于一次只能移动一张的情况就比较麻烦了，先证明存在至少一对相邻位置之间不移动纸牌的最优解。

因为相邻位置只会单向移动，所以所有相邻位置之间都有移动的某个解一定是如下形式：

绿色位置为移动的起点，红色位置为移动的终点。其中 $x$ 表示移动的纸牌数量，不妨设 $x_1$ 是最小的。

现在将 $x_1$ 置为 $0$，为了保持所有位置纸牌数量不变，反方向的移动数量需要增加 $x_1$，同方向的移动数量需要减少 $x_1$。图中 $x_2,x_3,x_7,x_9,x_{10}$ 增加，$x_4,x_5,x_6,x_8$ 减少。

因为 $x_1$ 是最小的所以不会出现负数。如果这样调整后增加的多于减少的，就将 $x_1$ 增加到 $x_1\times 2$，这样同样不会出现负数，并且增加减少刚好相反，移动总量会减少。

所以不断进行调整，在某个 $x$ 变为 $0$ 之前移动总量一定不会增加。

然后就同样可以破坏成链了，设位置 $k$ 与 $k+1$ 之间断开，移动总量为

\[\sum_{i=k+1}^n\left|(i-k)\times\overline s-\sum_{j=k+1}^i a_j\right|+\sum_{i=1}^k\left|(i+n-k)\times\overline s-\sum_{j=1}^i a_j-\sum_{j=k+1}^n a_j\right| \]

记 $a$ 的前缀和数组为 $pre$

\[\sum_{i=k+1}^n|pre_i-pre_k-(i-k)\times\overline s|+\sum_{i=1}^k|pre_n-pre_k+pre_i-(i+n-k)\times\overline s| \]

令 $a_i\gets a_i-\overline s$

\[\sum_{i=k+1}^n|pre_i-pre_k|+\sum_{i=1}^k|pre_n-pre_k+pre_i| \]

因为 $pre_n=0$，所以化简成

\[\sum_{i=1}^n|pre_i-pre_k| \]

显然 $pre_k$ 取中位数时最小。