BZOJ1045 - Click Here
Description
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。
Input
第一行一个正整数n<=1000000，表示小朋友的个数。
接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数。
Output
求使所有人获得均等糖果的最小代价。
Solutions
$i$向$i+1$传递$x$个糖果可以看做$i+1$向$i$传递$-x$个糖果，因此可以认为每个人只能向左传递。
设$x_i$表示$i$向$i-1$传递的糖果数，则答案为$\sum \mid x_i \mid$
考虑第$1\leq i \leq n - 1$个小朋友，其最后的糖果数必须满足$a_i-x_i+x_{i+1}=\overline{a}$，即$x_{i+1} = x_i + \overline{a} - a_i$
设$C_i = a_i - \overline{a}$，则上式等价于$x_{i+1} = x_i - C_i$，通过归纳法可得$x_{i+1} = x_1 - \sum_{k=1}^{i} C_i$
显然，对于第$n$个小朋友亦满足上诉等式。
这时，答案转换成$\sum_{i=0}^{n-1} \mid x_1 - \sum_{j=1}^i C_j \mid$，而题目的要求是最小化这个值。
注意到该和式的几何意义是，$x_1$与$n$个点的距离之和。因此问题转换成，给定数轴上$n$个点，寻找一个到他们距离之和最小的点。
不难看出，这个点正是这$n$个点的中位数，因此排序后直接计算即可。
$O(n \, log \, n)$
CODE
CODE - Click Here