算法/复杂度

据说是贪心的经典题目，背背模板吧，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 = 1 ; 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;

}