Description
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
Input
第一行一个正整数nn<=1’000’000，表示小朋友的个数． 接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．
Output
求使所有人获得均等糖果的最小代价。
Sample Input
4
1
2
5
4
Sample Output
4
题解
设a[i]表示第i个人给了第i+1个人多少
设s[i]表示第i个人原本有多少个
容易看出最后每个人的糖果数都是平均数
可列方程
s[1]+a[n]-a[1]=avg
s[2]+a[1]-a[2]=avg
….
s[n]+a[n-1]-a[n]=avg
移项可得
a[1]=s[1]+a[n]-avg
a[2]=s[2]+a[1]-avg=s[2]+s[1]+a[n]-2*avg
a[3]=s[3]+a[2]-avg=s[3]+s[2]+s[1]+a[n]-3*avg
…
把a[n]延后，可发现前面项均为前缀和减去平均数形式，设他们为C[i]
问题可变为求sigma(a[n]-C[i])
C数组为定值，原问题仍可转化为在数轴上有n个点，选一个点使得这n个点到这个点的总距离最小
容易看出这个点是中位数
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
int n;
LL a[1110000],avg;
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld",&a[i]),avg+=a[i];avg/=n;for(int i=1;i<=n;i++)a[i]=a[i-1]+a[i]-avg;sort(a+1,a+1+n);int tmp=n/2+1;LL ans=0;for(int i=1;i<=n;i++)ans+=abs(a[tmp]-a[i]);printf("%lld\n",ans);return 0;
}