MathLabs

第5题

nn 个人围坐成圈,共分配 nknk 枚硬币但不一定平均。一步是相邻两人之间转移一枚硬币。求一个用最少步数使每人硬币数相同的算法。
第 5/5 步:比较跨环移动并迭代
X→0X\to0
详细分析

若跨环操作没有更大收益,就重复下降操作直到 X=0X=0。同时计算沿边 XX 两个方向转移时 XX 的变化;若某方向能使它减少超过一单位,就选择减少更多的方向。每一步都合法且使 XX 严格下降,因此过程最终达到均等持有,并由势能论证知步数最少。 n,1n,1