数学/思维 UVA 11300 Spreading the Wealth

题目传送门

/*
    假设x1为1号给n号的金币数(逆时针)，下面类似
    a[1] - x1 + x2 = m(平均数)  得x2 = x1 + m - a[1] = x1 - c1; //规定c1 = a[1] - m，下面类似
    a[2] - x2 + x3 = m ,x3 = m + x2 - a[2] = m + (m + x1 - a[1]) - a[2] = 2 * m + x1 - a[1] - a[2] = x1 - c2;
    a[3] - x3 + x4 = m ,x4 = m + x3 - a[3] =............................= 3 * m + x1 - a[1] - a[2] - a[3] = x1 - c3;
    而我们求得是|x1|＋|x2|+|x3|+....+|xn|
    把上边的公式带入，每一项都会变成|x1 - ci|的形式，那就变成了：在数轴上有ｎ个点，求到他们的距离和最小的点是谁？
    然后结论是x1 = ci的中位数。
    中位数证明：http://blog.csdn.net/zhengnanlee/article/details/8915098
*/
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;

const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int a[MAXN], c[MAXN];

int main(void)        //UVA 11300 Spreading the Wealth
{
    //freopen ("UVA_11300.in", "r", stdin);

    int n;
    while (scanf ("%d", &n) == 1)
    {
        long long sum = 0;    int ave = 0;
        for (int i=1; i<=n; ++i)
        {
            scanf ("%d", &a[i]);
            sum += a[i];
        }
        ave = sum / n;
        c[0] = 0;
        for (int i=1; i<=n; ++i)
        {
            c[i] = c[i-1] + a[i] - ave;
        }

        sort (c+1, c+1+n);
        int x = c[n/2];    long long ans = 0;
        for (int i=1; i<=n; ++i)    ans += abs (x - c[i]);

        printf ("%lld
", ans);
    }

    return 0;
}