1045: [HAOI2008] 糖果传递
http://www.lydsy.com/JudgeOnline/problem.php?id=1045
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1416 Solved: 658
[Submit][Status]
Description
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
Input
小朋友个数n 下面n行 ai
Output
求使所有人获得均等糖果的最小代价。
Sample Input
4
1
2
5
4
Sample Output
4
数据规模
30% n<=1000
100% n<=1000000
交换糖果的方式为：（人给人）1给n，2给1,3给2，...，n给n-1.
ave为最终期望每人拥有的糖果数.
a[i]为第i个人拥有的糖果数，下标从1开始。
b[i]表示第i个人需要给第i-1个人的糖果数，允许为负。
假设第一个小朋友给第n个小朋友k个糖果，则
b[1]=k。
由a[1]-b[1]+b[2]=ave（原来的-送出的+新得到的=最终期望）得：
b[2]=b[1]-a[1]+ave;一般表达式为b[i]=b[i-1]-a[i-1]+ave;通项公式为：
b[i]=k- (求和（下标：1）（上标i-1）(表达式：a[i]))+(i-1)*ave;
令c[i]=(求和（下标：1）（上标i）(表达式：a[i]))-i*ave;
则b[i]=k-c[i-1];
显然有c[n]=0;故b[1]=k=k+c[n];
总的代价为：求和（下标：1）（上标n）(表达式：|b[i]| )
等于：求和（下标：1）（上标n）(表达式：|k-c[i]| );
可转化为数轴上有n个点，求某点到其他所有点线段和的最小值。
故对c[]数组排序，找出中位数即可；若有偶数个，取中间两个任意一个都可以。
