题目描述

有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为 1。

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

输入格式
第一行输入一个正整数 n，表示小朋友的个数。

接下来 n 行，每行一个整数 a[i]，表示第 i 个小朋友初始得到的糖果的颗数。

输出格式
输出一个整数，表示最小代价。

数据范围
1≤n≤1000000,
0≤a[i]≤2×109,
数据保证一定有解。

样例

输入样例：
4
1
2
5
4
输出样例：
4

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
LL s[N], c[N];

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

    // 预处理前缀和
    for (int i = 1; i <= n; i ++) {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    LL b = s[n] / n; // b是平均数
    int k = 0; // 预处理c
    for (int i = 1; i < n; i ++) c[k ++] = b * i - s[i];
    c[k ++] = 0; // c[n] = 0;

    // 比sort()快 O(nlogn)降低到O(n)
    nth_element(c, c + k / 2, c + k); // 求中位数
    LL res = 0;
    for (int i = 0; i < k; i ++)
        res += abs(c[i] - c[k / 2]);


    printf("%lld", res);

    return 0;
}

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;

public class Main {
    private static int n;
    private static long[] s, c;
    private static BufferedReader reader;
    private static PrintWriter writer;
    public static void main(String[] args) throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new PrintWriter(System.out);

        n = Integer.parseInt(reader.readLine());
        s = new long[n + 1];
        c = new long[n];
        // 预处理前缀和
        for (int i = 1; i <= n; i ++) {
            s[i] = Long.parseLong(reader.readLine());
            s[i] += s[i - 1];
        }

        reader.close();

        long b = s[n] / n;
        int k = 0;
        // 预处理c[0] ~ c[n-1]
        for (int i = 1; i < n; i ++) {
            c[k ++] = i * b - s[i];
        }
        c[k ++] = 0; // 即c[n] = 0

        Arrays.sort(c);
        long res = 0;
        for (int i = 0; i < k; i ++) {
            res += Math.abs(c[i] - c[k / 2]);
        }

        writer.print(res);
        writer.flush();
        writer.close();
    }
}

}