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; }