如果你看不懂题解
查看原帖
如果你看不懂题解
801322
Womind楼主2023/11/2 09:40

我也看不懂,可能我太菜了,大脑自动不准我看懂QAQ

用 cj=∑i=1jai−j∗avec_j=\sum\limits_{i=1}^j a_i-j*ave 表示每个点要传的纸牌, 然后选择其中的中位数,实质是选一个点,她不进行纸牌(金币)的传递。(因为她最后加的答案为零

可以证明环形均分纸牌问题必定至少有两个相邻的人不需要从别人那里获得纸牌:

每个人传 cj=∑i=1jai−j∗avec_j=\sum\limits_{i=1}^j a_i-j*ave 最后一个人一定传的是零 因为都是总数,环形的话无论从哪个点开始都一样。

现在唯一的问题是为什么断环为链不需要比如从 i=3i=3 断开 (这就说明 c3c_3 是最后一个点) c2c_2 不需要等于a3+a4+a5+⋯+an+a1+a2−(n−1)∗avea_3+a_4+a_5+\dots+a_n+a_1+a_2 - (n-1)*ave 而是 −a3+ave-a_3 + ave (前面的点一样)

感性的理解:(理解什么,她们就是等价的)

所以题解之所以没看懂,是因为题解在思路上跳了几步。

我可能在思路上也有跳步,如有错误,或更好的解释或衔接,欢迎在评论区说出QwQ。

2023/11/2 09:40
加载中...