标签归档:题解

UVa 11300 Spreading the Wealth 题解

UVa 11300, 此题用了代数法转换模型为:给定数轴上的n个点,求某一点使得到该数轴上各点距离之和最小。

令x[i]表示第i个人给了第i-1个人多少金币。特别地,x[1]表示第一个人给第n个人的。

令M表示最后每人赢得的金币数即平均值。

a[i]表示开始时所持金币数。

则有:

x1 = x1

x2 = M – a[1] + x[1] = x1 + M – a[1]

x3 = M – a[2] + x[2] = 2M – a[1] – a[2] + x[1]

x4 = M – a[3] + x[3] = 3M – a[1] – a[2] – a[3] + x1

令C[n] = sigma(a[i]) – n*m

则有 x[n] = x1 – c[n]

所求问题转化为:求x[1]使得 |x1| + |x1- C[1]| + |x1 – C[2]| … |x1 – C[n-1]|最小。

# include <iostream>
# include <cstdio>
# include <algorithm>
# define rep(i, n, x) for ( int i = 0; i < n; i+=x )
using namespace std;

int n;
long long A[1000007], sum, M, C[1000007];
long long ans;

long long labs(long long a)
{
    return a > 0LL ? a: -a;
}

int main()
{
    while ( cin >> n )
    {
        sum = 0;
        rep(i, n, 1)
        {
            scanf("%d", &A[i]);
            sum += A[i];
        }
        M = sum / n;
        C[0] = 0;
        for (int i = 1; i < n; ++i )
            C[i] = C[i-1] + A[i] - M;
        sort(C, C+n);
        int p = (n+1)>>1;
        ans = 0;
        rep(i, n, 1)
            ans += labs( C[p] - C[i]);
        cout << ans << endl;
    }
    return 0;
}