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