MathLabs

第5题

nn 个人围坐成圈,共分配 nknk 枚硬币但不一定平均。一步是相邻两人之间转移一枚硬币。求一个用最少步数使每人硬币数相同的算法。
第 4/5 步:处理前缀为零的情形
dj≥0,d1+⋯+dj−1<0d_j\ge0,\qquad d_1+\cdots+d_{j-1}<0
详细分析

在前缀和为零的情形,取满足 dj≥0d_j\ge0 的最小 j>i+1j>i+1。由于偏差总和为零,这样的 jj 存在。从第 jj 个人向第 j−1j-1 个人转移一枚硬币;直到 j−1j-1 的负前缀和向零增加一单位,因此 XX 减少一。该操作仍保持 d1≥0d_1\ge0。