uva 11300-Spreading the Wealth(分金貨)

代数解析:::
まず平均数aveを算出して分析を始めました
誰もが与えたものと与えたものの2つの部分しかなく、数字で表すとマイナス1プラスになります.
1番席の人は4番と2番にしか連絡がないので、x 1は1が4を、同じ理屈でx 2は2が1を表す.
x 1<0の場合は4が−x 1個の金貨を与えたことを示す.
1:A 1-x 1+x 2=ave->x 2=ave-A 1+x 1=x 1-C 1(Cは定数)
2: A2-x2+x3=ave -> x3 = ave-A2+x2 = ave-A2+x1-C1=x1-C2
3: A3-x3+x4=ave -> x4 = ave-A3+x3 = ave-A3+x1-C2=x1-C3
.....
n: An-xn+x1=ave -> xn = ave-An+x1 = ave-An+x(n-1)=x1-Cn
我々の目的は|x 1|+|x 1-C 1|+|x 1-C 2|+...|xn-Cn|の最小値、
上記式は、x 1から0、C 1、C 2...を要求点x 1と見なすことができる.Cnの距離が一番短い.
そして最小値を求めればいいです.これが代数解析です.
とても実用的な问题の难易度を下げることができる考え方の1つ...
コードは次のとおりです.

#include <cstdio>
#include <algorithm>
using namespace std;
#define M 1000010
long long a[M], c[M];
int main ()
{
    long long n, sum, ave;
    while(scanf("%lld",&n)==1)
    {
        sum = 0;
        for(int i = 1; i <= n; i++) {scanf("%lld",&a[i]); sum+=a[i];}
        ave = sum/n; c[0] = 1;
        for(int i = 1; i <= n; i++) c[i] = c[i-1]+a[i]-ave;
        sort(c,c+n);
        long long x1 = c[n/2], ans = 0;
        for(int i = 0; i < n; i++) ans+=abs(x1-c[i]);
        printf("%lld
",ans);
    }
    return 0;
}