题目简介
题目描述
有\(n\)个小朋友坐成一圈，每人有\(a_i\)个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为\(1\)。
输入
第一行一个正整数\(n\leq 10^6\)，表示小朋友的个数．接下来\(n\)行，每行一个整数\(a_i\)，表示第\(i\)个小朋友得到的糖果的颗数。
输出
求使所有人获得均等糖果的最小代价。
传送门
可以先做一下「NOIP2002 提高组」均分纸牌——题解(遇上一个强迫症人——怎么均分纸牌)
数学分析
我们统一以向左为正方向。
假设第\(i\)个小朋友会左传\(|b_i|\)个糖果（不论 \(b_i\) 的正负性），
那么第\(i(i<n)\)个小朋友会收到来自右边的\(|b_{i+1}|\)个糖果，而第n个小朋友会收到来自右边的\(|b_1|\)个糖果。
设\(a_{1\sim n}\)的平均数(average)为 \(ave\)
即
稍微变个形：
\[b_2=ave+b_1-a_1 \] \[b_3=ave+b_2-a_2=ave+(ave+b_1-a_1)-a_2=2\times ave+b_1-(a_1+a_2) \]同理得：
\[b_4=ave+b_3-a_3=3\times ave+b_1-(a_1+a_2+a_3) \] \[…… \] \[b_k=(k-1)\cdot ave+b_1-\sum_{i=1}^{k-1}a_i \] \[b_n=(n-1)\cdot ave+b_1-\sum_{i=1}^{n-1}a_i \]那么\(b_1\)呢？
\[b_1=n\cdot ave+b_1-\sum_{i=1}^{n}{a_i} \]这时我们假设一个\(c\)数组：
\[c_1=a_1-ave\Rightarrow b_2=b_1-(a_1-ave)=b_1-c_1 \] \[c_2=a_1+a_2-2\times ave\Rightarrow b_3=b_1-c_2 \] \[c_3=a_1+a_2+a_3-3\times ave\Rightarrow b_4=b_1-c_3 \] \[…… \] \[c_k=\sum_{i=1}^{k}{a_i}-k\cdot ave\Rightarrow b_k=b_1-c_k \] \[c_n=\sum_{i=1}^{n}{a_i}-n\cdot ave\Rightarrow b_n=b_1-c_n \]本题要求付出的代价最小。
即要求$$\sum_{i=1}^{n}{|b_i|}$$最小。
又
\[\sum_{i=1}^{n}{|b_i|}=\sum_{i=1}^{n}{|b_1-c_i|} \]因为\(c_i\)很好求出，所以此时我们只需要找到一个合适的\(b_1\)使\(b_1\)到\(c_i\)距离和最小。
或许你已经想到了。
没错——中位数
看看简短的代码吧
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000010;
int n;
ll a[maxn];
ll c[maxn];
ll myabs(ll x){return x<0?-x:x;}
int main(){
cin>>n;
ll ave=0;
for(int i=1;i<=n;i++){
cin>>a[i];
ave+=a[i];
}
ave/=n;
for(int i=1;i<=n;i++)
c[i]=c[i-1]+a[i]-ave;
sort(c+1,c+n+1);
ll k=c[(n+1)>>1];
ll ans=0;
for(int i=1;i<=n;i++)
ans+=myabs(k-c[i]);
cout<<ans;
return 0;
}