题目描述

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

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

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

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

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

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

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

数据范围
1≤n≤1000000

样例

输入样例：
4
1
2
5
4
输出样例：
4

题解

交换糖果的方式为：（人给人）1给n，2给1,3给2，…，n给n-1.
ave为最终期望每人拥有的糖果数.
a[i]为第i个人拥有的糖果数，下标从1开始。
b[i]表示第i个人需要给第i-1个人的糖果数，允许为负。
假设第一个小朋友给第n个小朋友k个糖果，则
b[1]=k。
由a[1]-b[1]+b[2]=ave（原来的-送出的+新得到的=最终期望）得：
b[2]=b[1]-a[1]+ave;一般表达式为b[i]=b[i-1]-a[i-1]+ave;通项公式为：
b[i]=k- (求和（下标：1）（上标i-1）(表达式：a[i]))+(i-1)ave;
令c[i]=(求和（下标：1）（上标i）(表达式：a[i]))-iave;
则b[i]=k-c[i-1];
显然有c[n]=0;故b[1]=k=k+c[n];
总的代价为：求和（下标：1）（上标n）(表达式：|b[i]| )
等于：求和（下标：1）（上标n）(表达式：|k-c[i]| );
可转化为数轴上有n个点，求某点到其他所有点线段和的最小值。
故对c[]数组排序，找出中位数即可；若有偶数个，取中间两个任意一个都可以。

算法1

(数学问题)

C++ 代码

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1000000 + 10;
int a[N], c[N];
int main()
{
    int n, i;
    while(~scanf("%d",&n))
    {
        LL sum = 0;
        for(i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
            sum += (long long)a[i];
        }
        LL ave = sum / n;
        c[1] = 0;
        for(i = 2; i <= n; i++)
            c[i] = c[i-1] + a[i] - ave; 
        sort(c+1,c+n+1);
        LL ans = 0;
        int mid = c[n/2+1];  //中位数
        for(i = 1; i <= n; i++)
            ans += abs(c[i] - mid);  //距离和
        printf("%lld\n",ans);
    }
    return 0;
}