《算法竞赛进阶指南》[HAOI2008] 糖果传递--题解

题目描述
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

输入描述:
第一行一个正整数n ≤ 987654321，表示小朋友的个数．
接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．

输出描述:
求使所有人获得均等糖果的最小代价。

思路：
开始是n个小孩围成一圈，第i个小孩有ai个糖果（可以自己画个图）。他们的平均值ave就是：总的糖果数/n。可以用Xi表示第i个小孩给了第i-1个小孩Xi个糖果（即，第1个小孩给了第n个小孩X1个糖果，第二个小孩给了第一个小孩X2个糖果）。如果Xi为负数，反过来就是索取了Xi个糖果。
我们这里可以推导出：

由上面又可以推出来：

要把这些看成：

我们要算这些每一个左边绝对值的和，在数轴上也就是每个点与点之间的距离.
...
不多说了，上代码
完整C++版AC代码：

#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef long long ll;
const int N = 1000010;
int n;
ll a[N];


int main() {
    cin >> n;
    ll ave = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        ave += a[i];
    }
    ave = ave / n;
    for (int i = n; i > 1; i--) {
        a[i] = a[i] - ave + a[i + 1];
    }
    a[1] = 0;
    sort(a + 1, a + n + 1);

    ll res = 0;
    for (int i = 1; i <= n; i++) res += abs(a[i] - a[(n + 1) / 2]);//绝对值
    cout << res << endl;
    return 0;
}