题解 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;
}
```