这几天除了照常刷版题外还复习了下线段树和重读组合数学那本书，还了下补题。还是先整理下牛客比赛两个题目，公式推导对我来说确实有些难度，感觉自己组合问题还是太菜了。
平分游戏
题目：
集训队一共有n位同学，他们都按照编号顺序坐在一个圆桌旁。第i位同学一开始有a[i]个硬币，他们希望使得每位同学手上的硬币变成相同的数目。每一秒钟，有且仅有一位同学可以把自己手上的一枚硬币交给另一位同学，其中这两位同学中间必须间隔k位同学。现在问的是最少几秒后所有同学手上的有相同数量的硬币。
来自：https://blog.csdn.net/hnust_Derker/article/details/79684711
思路：先看怎么处理一个圈有n个人只给相邻的人硬币的解法，保证总数整除n是必然的，有个很明显的情况就是如果A给了B，那么B将不会再给A，这样无疑是多余的步骤，所以相邻的两个人AB之间要么是A给B，要么是B给A，那么相邻的第i−1，i，i+1三个人，不妨假设第i个人给了第i−1个人xi个硬币，从第i+1个人中拿到了xi+1个硬币，其中xi−1可以是负数，代表是i−1给i硬币，假设最终每个人有M个硬币，初始状态第i个人有ai个硬币，那么有以下等式：
对于第一个人，a1−x1+x2=M ⇒ x2=M−a1+x1=x1−C1(C1=a1−M,下面类似)
对于第二个人，a2−x2+x3=M ⇒ x3=M−a2+x2=2M−a1−a2+x1=x1−C2
........
所有式子带入之后其实就是求|x1|+|x1−C1|+|x1−C2|+....+|x1−Cn−1|的最小值，这个其实就是在一个坐标轴上找一点x使得x和0,C1,C2..Cn−1的距离之和最短，这个是求中位数，对这些数排序一下x取中位数就好了
现在看有n个人隔k个人才能给硬币，其实这个可以看做gcd(n,k+1)个圈，然后他们之间相邻的两个人可以交换硬币，第1个人依次和1+(k+1),1+2(k+1)...形成一个圈，剩余的人也是这样，这样就是处理gcd(n,k+1)个圈就是了，最终结果全部相加就是答案，注意一些特殊情况，k=n−1或者k=n其实是不能交换的状态，这个特判一下就好了
这几天还是有些急躁，刷板题的时候一些水题总是跳很长时间才调通，推导数学类的题目总是思路打不开。估计还是太菜了，必须加把劲。