糖果传递

题目描述

思路

代码

#include <cstdio>
#include <cmath>
#include <algorithm>

long long n,avg,tot,arr[1000005],ans;
inline long long int read() {
    long long s = 0,f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
    return s * f;
}
int main() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        arr[i] = read(),tot += arr[i];
    }
    avg = tot / n;
    for (int i = 1; i <= n; ++i) {
        arr[i] -= avg,arr[i] += arr[i - 1];
    }
    std::sort(arr + 1,arr + n + 1);
    for (int i = 1,j = n >> 1; i <= n; ++i) {
        ans += abs(arr[i] - arr[j]);
    }
    printf("%lldn",ans);
    return 0;
}