其实这题和A118挺像的,只不过那题是一条链,而这题是一个环,但是思想都一样,都是用平均数来做文章。
想象一堆牌围成一圈,在脑中模拟分牌过程,你会发现一个性质:必定至少有两堆相邻的牌不需要从别的纸牌堆那里获得纸牌。
于是,我们可以利用这个性质,把环破坏成链,枚举不需要交换纸牌的那两堆纸牌,将其分别放在链的第一个位置与最后一个位置。
最后按开始的序列顺序,像普通均分纸牌一样预处理出 bbb 数组。设枚举的位置为 kkk,平均数为 sumsumsum,bib_ibi 设为 ai−suma_i-sumai −sum 的前缀和,则题目就是求 ans=∑∣bk−bi∣ans=\sum \left|b_k-b_i\right|ans=∑∣bk −bi ∣ 的最小值了。根据初中的知识可得当 kkk 为 n+12\frac{n+1}{2}2n+1 时 ansansans 的值最小。
建议将为普及- 或者 普及/提高-,这题并不难。