题目描述

blablabla

样例

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

typedef long long LL;

int n;
int a[N];
LL c[N];

int main()
{
    cin >> n;

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

    LL sum = 0;

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

    for(int i = n;i > 1;i --)
    {
        c[i] = c[i + 1] + avg - a[i];//c[i] = c[i + 1] - avg + a[i];
    }
    c[1] = 0;

    sort(c + 1,c + n + 1);

    LL res = 0;
    for(int i = 1;i <= n;i ++) res += abs(c[i] - c[(n + 1)/2]);

    printf("%lld\n",res);
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla