题目描述

blablabla

样例

#include<iostream>
#include<algorithm>
#include<cmath>

#define int long long

using namespace std;
int n;
const int N = 1e6 + 10;
int a[N];
int c[N];

signed main()
{
    cin >> n;
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    int avg = sum / n;
    /*
        一个环，每个人去传递一个常数给下一个人，可以是负的也可以是正的即表示是加还是减\
        假定xn代表a_n + 1 给 a_n的糖果数，可正可负
        结果就是min(|x1| + |x2| + ......)

        a_1 + x1 - xn = avg  第一个人加上自己给出的以及自己得到的就是平均数
        a_2 + x2 - x1 = avg
        a_3 + x3 - x2 = avg
        ...
        a_n + xn - x1 = avg


        通过联立可以得到

        x1 = xn - a_1 + avg
        x2 = xn - a_1 - a_2 + 2 * avg
        x3 = xn - a_1 - a_2 - a_3 + 2*avg
        ...
        xn-1 = xn - a_1 - a_2 -a_3 -....+(n-1)*avg
        xn = xn

        而我们前面知道最后的结果是全部加起来
        转换成min(xn - a_1 + avg + xn - a_1 - a_2 + 2*avg +.....xn)
        我们定义一个数组c[i] = a_1 + a_2 + a_3 +....+a_i - i*avg
        c[0] = 0
        即c就是一个前缀和数组减去了一个平均数乘i
        最后其实就是min(xn - c[1] + xn - c[2] + .... xn - c[n - 1]
        这个xn可以为任何数，当这个xn为c数组的这个数轴上的中位数时，那么就能得到最小值，因为是一个距离问题

    */
    for (int i = 2; i <= n; i++)
    {
        c[i] = c[i - 1] + a[i] - avg;
    }

    sort(c + 1, c + n + 1);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += abs(c[i] - c[(n + 1) / 2]);
    }
    cout << ans << endl;
}

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla