「HAOI2008」糖果传递 - 数学

个小朋友坐成一圈,每人有 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 。求使所有人获得均等糖果的最小代价。

链接

BZOJ 1045

题解

表示第 个人给第 个人的数量,则有

我们的目标是最小化

,则

即,最小化

问题转化为,在数轴上找一个点,到给定一些点的距离之和最小。答案即为 的中位数。

代码

#include <cstdio>
#include <algorithm>

const int MAXN = 1000000;

int main() {
    int n;
    scanf("%d", &n);

    static long long a[MAXN];
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
        sum += a[i];
    }

    long long avg = sum / n;
    static long long c[MAXN];
    c[0] = 0;
    for (int i = 1; i < n; i++) c[i] = c[i - 1] - a[i] + avg;

    std::sort(c, c + n);

    long long mid = c[n / 2], ans = 0;
    for (int i = 0; i < n; i++) ans += llabs(c[i] - mid);

    printf("%lld\n", ans);

    return 0;
}