糖果传递

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

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

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

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

输入格式

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

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

输出格式

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

[HTML_REMOVED]

数据范围

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

输入样例

4
1
2
5
4

输出样例

4

算法/复杂度

据说是贪心的经典题目，背背模板吧，hhhhh

思路：

1. 题目默认每次只能给左边的人或者右边的人。同样， 最优解一定是没有来回的。所以，全局来看，两个小朋友间的给予关系，可以用一条单向线表示。

1. 为了让每个人的糖果分的一样多，那么x1, x2 ,x3.....的取值就是这样子的

1. 然后根据数学原理 X1 取 A B C D E 的中位数，可令距离和最小。

（不懂的百度货仓选址问题）

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[1000010],p[1000010],x1,n;
ll ai =0,res = 0;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        //cin>>a[i] 4806 ms
        scanf("%d",&a[i]);//2320 ms
        ai+=a[i];
    }
    //求平均值
    ai/=n;
    //求那几个推导出来的理论点
    p[1] = 0;
    for(int i = 2 ; i <= n; i++)
        p[i] = p[i-1] + ai - a[i];

    //取中位数
    sort(p+1,p+n+1);
    if(n%2==0) x1 = (p[n/2] + p[n/2+1])/2;
    else x1 = p[n/2];

    //求距离和
    for(int i = 1 ; i <= n  ; i++)
        res += abs(x1 - p[i]);

    cout<<res<<endl;
    return 0;

}