[HAOI2008] 糖果传递

A1 + X1 - X2 = G

A2 + X2 - X3 = G

An + Xn - X1 = G

解得

X1 = X1

X2 = A1 - G + X1

X3 = A1 + A2 - G - G + X1

Xn = sigma(1, n)A - n * G + X1

注意到ans = abs (X1 - lamda1) + abs (X2 - lamda2) + ... + abs (Xn - lamdan)

于是sort 取中位数

代码丑极了替换的

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <algorithm>
 4 using namespace std;
 5 const long long N = 2001000;
 6 long long a[N], s[N], tar[N], n;
 7 int main ()
 8 {
 9     scanf ("%d", &n);
10     for (long long i = 1; i <= n; i ++)
11         scanf ("%d", &a[i]), s[i] = s[i - 1] + a[i];
12     long long g = s[n] / n;
13     for (long long i = 1; i <= n; i ++)
14         tar[i] = i * g - s[i];
15     sort (tar + 1, tar + 1 + n);
16     long long x = n >> 1, z (0);
17     for (long long i = 1; i <= n; i ++)
18         z += abs (tar[i] - tar[x]);
19     printf ("%lld\n", z);
20     return 0;
21 }