！

https://www.acwing.com/file_system/file/content/whole/index/content/1744436/

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[] a = new int[n + 2];
        long sum = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
            sum += a[i];
        }

        int avg = (int) (sum / n);

        int[] c = new int[n + 2];
        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 ans = 0;
        for (int i = 1; i <= n; i++) ans += Math.abs(c[i] - c[(n + 1) / 2]);

        System.out.println(ans);
    }
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla