首先,最后每个小朋友手中的糖果数都可以算出来,是总和 $sum$ 除以人数 $n$,也就是 $n$ 个小朋友糖果的平均数,用 $ave$ 来表示。
我们假设编号为 $i$ 的小朋友手中有 $a_i$ 颗糖果,第 $i$ 个小朋友给了第 $i - 1$ 个小朋友 $x_i$ 颗糖果,其中,如果 $x_i < 0$,则说明第 $i - 1$ 个小朋友给了第 $i$ 个小朋友 $x_i$ 颗糖果,$x_1$ 表示第 $1$ 个小朋友给第 $n$ 个小朋友的糖果数。所以最后答案就是 $|x_1| + |x_2| + |x_3| + … + |x_n|$。
对于第 $1$ 个小朋友,他给了第 $n$ 个小朋友 $x_1$ 个糖果,还剩下 $a_1 - x_1$ 个糖果,又因为第 $2$ 个小朋友给了他 $x_2$ 颗糖果,所以他最后剩下 $a_1 - x_1 + x_2$ 颗糖果。我们得到一个方程:$a_1 - x_1 + x_2 = ave$。
同理对于第 $2$ 个小朋友,我们可以推出方程 $a_2 - x_2 + x_3 = ave$。
以此类推,最后我们可以得到 $n$ 个方程,但因为前 $n - 1$ 个方程可以推出第 $n$ 个方程,所以实际上只有 $n - 1$ 个方程有用。
虽然我们无法直接解出答案,但可以用 $x_1$ 表示其他的 $x_i$。
我们假设 $b_1 = a_1 - ave$,$b_i = a_i + b_{i - 1} - ave$。
对于第 $1$ 个小朋友,$a_1 - x_1 + x_2 = ave$ $\Rightarrow$ $x_2 = ave - a_1 + x_1 = x_1 - b_1$。
同理,对于第 $2$ 个小朋友,$a_2 - x_2 + x_3 = ave$ $\Rightarrow$ $x_3 = ave - a_2 + x_2 = 2ave - a_1 - a_2 + x_1 = x_1 - b_2$。
以此类推……
我们希望 $\sum\limits_{i = 1}^n{|x_i|}$ 最小,也就是 $|x_1| + |x_1 - b_1| + |x_1 - b_2| + … + |x_1 - b_{n - 1}|$ 要尽量小。我们注意到 $|x_1 - b_i|$ 其实可以看做数轴上 $x_1$ 和 $b_i$ 的距离。
所以题目就转变成了给定数轴上的 $n$ 个数,找到一个数,让给定的这些数到这个数的距离总和尽量小。这其实就是 货仓选址 问题,区中位数即可,具体证明见货仓选址题解。
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 1000010;
long long a[N];
int main()
{
long long n, sum = 0, ans = 0;
scanf("%lld", &n);
for (int i = 1; i <= n; i ++ )
{
scanf("%lld", &a[i]);
sum += a[i];
}
sum /= n;
for (int i = 1; i <= n; i ++ )
a[i] = a[i] - sum + a[i - 1];
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i ++ )
ans += abs(a[i] - a[(n + 1) / 2]);
printf("%lld", ans);
return 0;
}
stO 种花家的兔兔 Orz
Orz