750
糖果傳遞
1045: [HAOI2008] 糖果傳遞
https://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[]數組排序，找出中位數即可；若有偶數個，取中間兩個任意一個都可以。
最後更新：2017-04-03 12:55:46