Description

有 \(n\) 个小朋友坐成一圈, 每人有 \(a_i\) 个糖果. 每人只能给左右两人传递糖果. 每人 每次传递一个糖果代价为 \(1\).

Input

第一行一个正整数 \(n\), 表示小朋友的个数．接下来 \(n\) 行, 每行一个整数 \(a_i\), 表示 第 \(i\) 个小朋友得到的糖果的颗数.

Output

求使所有人获得均等糖果的最小代价.

Sample Input

4
1
2
5
4

Sample Output

4

Explanation

原题的 \(n\) 给成了 \(\leq 987654321\), 但是其实 \(1000000\) 就可以了, bzoj 巨坑, 但是 在这里我就给改掉了~

题解大概是这样的 (引用自黄学长):

首先, 最终每个小朋友的糖果数量可以计算出来, 等于糖果总数除以 \(n\), 用 \(mean\) 表示.

假设标号为 \(i\) 的小朋友开始有 \(a_i\) 颗糖果,\(x_i\) 表示第 \(i\) 个小朋友给了第 \(i-1\) 个小朋友 \(x_i\) 颗糖果, 如果 \(x_i \lt 0\), 说明第 \(i-1\) 个小朋友给了第 \(i\) 个小朋友 \(x_i\) 颗糖果,\(x_1\) 表示第一个小朋友给第 \(n\) 个小朋友的糖果数量. 所以最后的答案就是:

\[res = \sum_{i=1}^{n} |x_i|\]

对于第一个小朋友, 他给了第 \(n\) 个小朋友 \(x_1\) 颗糖果, 还剩 \(a_1 - x_1\) 颗糖果; 但因为第 \(2\) 个小朋友给了他 \(x_2\) 颗糖果, 所以最后还剩 \(a_1 - x_1 + x_2\) 颗糖果. 根据题意, 最后的糖果数量等于 \(mean\), 即得到了一个方程:\(a_1 - x_1 + x_2 = mean\).

同理, 对于第 \(2\) 个小朋友, 有 \(a_2 - x_2 + x_3 = mean\). 最终, 我们可以得到 \(n\) 个方程, 一共有 \(n\) 个变量, 但是因为从前 \(n - 1\) 个方程可以推导出最后一个方程, 所以实际上只有 \(n - 1\) 个方程是有用的.

尽管无法直接解出答案, 但可以用 \(x_1\) 表示出其他的 \(x_i\), 那么本题就变成了单变量的极值问题.

对于第 1 个小朋友,\(a_1 - x_1 + x_2 = mean \longrightarrow x_2 = mean - a_1 + x_1 = x_1 - c_1\) (假设 \(c_1 = a_1 - mean\), 下同)

对于第 2 个小朋友,\(a_2 - x_2 + x_3 = mean \longrightarrow x_3 = mean - a_2 + x_2 = 2 \cdot mean - a_1 - a_2 + x_1 = x_1 - c_2\)

对于第 3 个小朋友,\(a_3 - x_3 + x_4 = mean \longrightarrow x_4 = mean - a_3 + x_3 = 3 \cdot mean - a_1 - a_2 - a_3 + x_1 = x_1 - c_3\)

\(\ldots\)

对于第 n 个小朋友,\(a_n - x_n + x_1 = mean\).

我们希望 \(x_i\) 的绝对值之和尽量小, 即 \(|x_1| + |x_1 - c_1| + |x_1 - c_2| + \ldots + |x_1 - c_{n-1}|\) 要尽量小. 注意到 \(|x_1 - c_i|\) 的几何意义是数轴上的点 \(x_1\) 到 \(c_i\) 的距离, 所以 问题变成了: 给定数轴上的 \(n\) 个点, 找出一个到他们的距离之和尽量小的点, 而这个点 就是这些数中的中位数, 证明略.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 1000100;

int n;
lli arr[maxn], sum, mean;

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &arr[i]);
        sum += arr[i];
    }
    mean = sum / n;
    for (int i = 2; i <= n; i++)
        arr[i] = arr[i - 1] + arr[i] - mean;
    sort(arr + 1, arr + 1 + n);
    lli res = 0,
        mid = arr[n / 2 + 1];
    for (int i = 1; i <= n; i++)
        res += abs(arr[i] - mid);
    printf("%lld", res);
    return 0;
}