题解 P4016 【负载平衡问题】
浅色调
2018-04-17 21:00:15
### 思路：
$\quad\quad$**贪心+数学**
$\quad$先来讲下普通均分纸牌问题：
普通均分纸牌问题就是$n$个小朋友排成一列，各自有$a[i]$张牌，每个人只能给相邻的人传递纸牌，问至少需要传递多少张纸牌才能使每个小朋友牌的个数相等。
设总牌数为$sum$（即$sum=\sum{a[i]}$），则每个人最后会各自有$T=\frac{sum}{n}$张牌，设$g[i]=T-a[i]$，则让前$k$个人牌数相同需要的交换牌数为$\sum\limits_{i=1}^{i\leq k}{|s[i]|}$，其中$s[i]=\sum\limits_{j=1}^{j\leq i}{g[i]}$，可以这样理解，要让前$k$个人牌数相同，要依次让前$1,2,3…k-1$个人牌数相同，多退少补，会与后边的人发生二者之差绝对值的牌数交换。所以移动总牌数$ans=\sum{|s[i]|}$。
再来讲下本题的环形均分纸牌问题：
环形均分纸牌问题就是$n$个小朋友围成了一圈（等同于第一人和最后一人相邻），这样的话其实可以同样的处理。
仔细思考环形均分纸牌问题可以发现一个性质：必定至少有两个相邻的人不需要从别人那里获得纸牌（这是显然的，不妨设这两个人的位置为$i$和$i+1$，则环形序列中必定有满足条件$a[i]\leq T\;\;a[i+1]\geq T$的两个相邻位置，这样$a[i],\;a[i+1]$之间没有交换，$a[i]\leq T$可以从$a[i-1]$获得纸牌，$a[i+1]\geq T$可以把多的纸牌给$a[i+2]$）。
于是由上面的性质，我们直接破环成链，枚举相邻的不需要交换纸牌的两人（将其分别放在第一和最后一个位置）。
按开始的序列顺序，像普通均分纸牌一样处理出$s$数组，那么假设枚举的位置为$k$，则类比普通均分纸牌求法，新的$s[i]=s[i]-s[k]$（注意$s$为前缀和），于是$ans=\sum{|s[i]-s[k]|}$，我们套用中学数学知识可知当$s[k]$为$s$中位数时，$ans$最小。于是本题就解决了。
$\quad$欢迎来踩博客：[five20](http://www.cnblogs.com/five20/p/8869948.html)（蒟蒻写题解不易，转载请注明出处）
### 代码：
```cpp
#include<bits/stdc++.h>
#define il inline
#define ll long long
using namespace std;
const int N=105;
ll n,a[N],sum,s[N];
int main()
{
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
sum/=n;
for(int i=1;i<=n;i++)a[i]-=sum,s[i]=s[i-1]+a[i];
sort(s+1,s+n+1);
sum=0;
for(int i=1;i<=n;i++)sum+=abs(s[n/2+1]-s[i]);
cout<<sum;
return 0;
}
```