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

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

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

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

输入格式

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

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

输出格式

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

数据范围

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

原题链接

122. 糖果传递 - AcWing题库

输入样例：

4
1
2
5
4

输出样例：

4

题解：

a【i】给前一个的糖果数量为x[ i ], (每一个 x 既可以是整数也可以是负数，因为既可以是前一个给后一个也可以是后一个给前一个)。最终目的就是使：x[1] + x[2] +…..+ x[n]之和最小。

公式详解：

(34条消息) 糖果传递-----（数学推导）_搬砖的小孩有肉吃的博客-CSDN博客

代码：

import java.io.*;
import java.util.*;

public class Main {

    static int[] a = new int[1000010];
    static long[] c = new long[1000010];
    public static void main(String[] args) {

        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        for(int i = 1; i <= n; i++)a[i] = cin.nextInt();

        long sum = 0;

        for(int i = 1; i <= n; i++)sum += a[i];

        long avg = sum / n;

        for(int i = n; i > 1; i--){
            c[i] = c[i + 1] + avg - a[i];
        }
        c[1] = 0;
        Arrays.sort(c, 1, n + 1);
        long res = 0;
        for(int i = 1; i <= n; i++){
            res += Math.abs(c[i] - c[(i + 1) / 2]);
        }
        System.out.println(res);
    }


}