题目描述

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

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

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

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

输入格式

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

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

输出格式

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

数据范围

1≤n≤1000000
数据保证一定有解。

输入样例：

4
1
2
5
4

输出样例：

4

主要考点

贪心

主要思路

目标为计算和: sum = |x1| + |x2| + |x3| + ···· |xn|
写出xi的表达式,经发现xn可以用含x1的式子表示,将xi用x1表示,寻找规律
转化为货仓寻址问题

C ++ 代码

#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1e6 + 10;

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

int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) scanf("%d", &a[i]);

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

    int ave = sum / n;  //求平均值
    for(int i = n - 1; i > 0; i --){
        c[i] = c[i + 1] + ave - a[i];
    }
    c[0] = 0;

    sort(c, c + n);

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

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

    return 0;
}