MathLabs

第5题

nn 个人围坐成圈,共分配 nknk 枚硬币但不一定平均。一步是相邻两人之间转移一枚硬币。求一个用最少步数使每人硬币数相同的算法。
第 3/5 步:选择使 XX 下降的移动
di+1<0,d1+⋯+di>0d_{i+1}<0,\qquad d_1+\cdots+d_i>0
详细分析

取第一个满足 di+1<0d_{i+1}<0 的 ii。若前缀 d1+⋯+did_1+\cdots+d_i 为正,就从第 ii 人向第 i+1i+1 人转一枚硬币;其绝对值减一而其他项不变。若此前缀不正,极小性迫使 d1=⋯=di=0d_1=\cdots=d_i=0。