有 \(n\) 个人排成一列（或一个环），第 \(i\) 个人手里有 \(c_i\) 张牌，在每一步操作中，可以让某人给他左边或右边的人一张牌，问最少多少步可以让每个人手中的牌数相等。
线性均分纸牌问题
首先定义 \(\texttt{avg}\) 为纸牌总数的平均数，如果 \(\texttt{avg}\) 不是整数的话，那么就是无解。否则如果要使每堆纸牌的数量一样多的话，那么经过移动后要使 \(A_i=\texttt{avg}\)。
对于第一堆牌，它只能向第二堆牌索取，或者进行给予。设 \(x=A_i-\texttt{avg}\)。如果 \(x>0\)，那么就把多的给第二堆。如果 \(x<0\)，不管怎么移动，必然有几步是第二堆给第一堆 \(\lvert x \rvert\) 张牌。上述两种情况答案需要增加。如果 \(x=0\)，就不用管了。
此时我们发现第一堆牌已经符合条件了，那么第一堆就可以直接忽略了，此时第二堆就变成了第一堆，继续重复上述步骤。
如何说明这样做是最优的呢？我们发现在上述过程中，每一步都是必须的，没有多余的步骤，所以其必然是最优解，这也是贪心思想的体现。
如果移牌的过程中出现负数怎么办？假设 \(c_i\) 在移动过程中是负数，那么接下来他一定会在 \(c_{i+1}\) 处拿牌。可以认为 \(i+1\) 向 \(i\) 给予牌是在 \(i\) 给予 \(i-1\) 牌之前，所以不影响结果。
对于统计答案，显然可以直接模拟，不过如果令 \(tot\) 是 \(c\) 的前缀和，可以发现让前 \(i\) 个人 \(c_i=\texttt{avg}\) 的代价就是 \(\sum\limits_{j=1}^{i} \lvert j*\texttt{avg}-tot_j \rvert\)，证明如下：
标签：纸牌,texttt,tot,问题,均分,avg,堆牌 From： https://www.cnblogs.com/zhuluoan/p/18409019