均分纸牌
首先看到这题,首先第一个人只能向右传,这样才能达到平均数。如果当前没有达到平均数,那只能向右传,因为左边都完成了要求。
负载平衡问题
糖果传递
Haybale Restacking G
负载平衡问题
图书馆书架上的书
现在是在一个环上,假设我们当前的数为a[i],要变成b[i]那么我们就可以假设所有数都向左传\(x_{i}\),那么就可以得出下列式子
\(a_{1}-x_{1}+x_{2}=b_{1}\)
\(a_{2}-x_{2}+x_{3}=b_{2}\)
\(.........\)
\(a_{n}-x_{n}+x_{1}=b_{n}\)
移项
\(x_{2}=b_{1}+x_{1}-a_{1}\)
\(x_{3}=b_{1}+b_{2}-a_{1}-a_{2}+x_{1}\)
\(.........\)
发现规律
\(x_{i}=abs(x_{1}+\sum_{j=1}^{i} b[j]-a[j])\)
\(x_{i}=abs(x_{1}-\sum_{j=1}^{i} a[j]-b[j])\)
要让\(\sum_{i=1}^{n} x_{i}\)最小,那么这其实就是在数轴上选一个点,使其到其他点的距离和最小,这个取中位数即可。