题目描述

Description
有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

Input
第一行一个正整数n<=1000000，表示小朋友的个数．

接下来n行，每行一个整数ai，表示第i个小朋友得到的糖果的颗数．

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

Sample Input
4
1
2
5
4

Sample Output
4

对于$30 \%$的数据，$n \leq 1000$
对于$100 \%$的数据，$n \leq 10^6$，保证答案可以用64位有符号整数存储。

题目解析

数学方式求解:

由题易得$avg = \Sigma_{i=1}^n a_i \div n$
从而假设，第$i$个人从第$i-1$个人手里拿到$x_i$个糖果，传递给第$i+1$个人$x_{i+1}$个糖果后达到了$avg$
$\implies avg = a_i + x_i - x_{i+1}\\
\therefore
avg = a_1 + x_1 - x_2\\
avg = a_2 + x_2 - x_3\\
avg = a_3 + x_3 - x_3\\
……\\
avg = a_n + x_n - x_1\\
$
$
\implies
x_2 = a_1 - avg + x_1\\
x_3 = a_2 - avg + x_2= (a_1+a_2) - 2\times avg + x_1\\
x_4 = a_3 - avg + x_3= (a_1+a_2+a_3) - 3\times avg + x_1\\
……\\
\implies x_n = \Sigma_{i=1}^{n-1} a_i - (n-1)\times avg + x_1 = \Sigma_{i=1}^{n-1} [a_i - avg] + x_1
$

故最后求得通项

$$\Large x_n = \Sigma_{i=1}^{n-1} [a_i - avg] + x_1$$

设$C_i = \Sigma_{i=1}^{n-1} [avg - a_i]$
$\therefore x_n = x_1 - C_i\\
\implies
x_1 = x_1 - C_0;\\
x_2 = x_1 - C_1;\\
x_3 = x_1 - C_2;\\
……\\
x_n = x_1 - C_{n-1};\\
$
此时，问题为求$min(\Sigma_{i=1}^n x_i)$,则通过以上步骤我们将问题转化成为了$x_1$到数列$C_i$各项的距离之和的最小值。也就是求数列$C_i$的中位数到数列各项的距离之和。

题解

#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll a[1000002],c[1000002] = {0};
int main() {
    ll n = 0,avg = 0;
    scanf("%ld",&n);
    
    for (ll i = 1; i <= n; i++){
        cin>>a[i];
        avg += a[i];
    }
    avg /= n;

    
    for (ll i = 1; i < n; i++)
        c[i] = (avg - a[i])+c[i-1];
    sort(c,c+n);

    ll ans=0,midle;
    if(n&1){
        midle=c[n/2];
    }
    else{
        midle=(c[(n-1)/2]+c[(n-1)/2+1])/2;
    }

    for(ll i=0;i<n;i++){
        ans+=abs(c[i]-midle);
    }
    cout<<ans<<endl;
    return 0;
}