122. 糖果传递(贪心)

https://www.acwing.com/problem/content/description/124/
求最小代价，且数据范围为1e6，大概是O(N)或O(NlogN)，大概就是排个序,贪心一般都是排序
设定每个小朋友给出的为xi，有如图

最后判断式子最小，只需要排序后ci都确定在数轴的位置上，寻找一个x在c中即可

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 1e6+10;
LL a[N],c[N];
LL res,sum;

int n;
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)cin >> a[i],sum+=a[i];
    LL avg = sum/n;
    for(int i=1;i<=n;i++)c[i]=c[i-1]+a[i]-avg;
    sort(c+1,c+n+1);
    for(int i=1;i<=n;i++)
    {
        res+= abs(c[i]-c[(i+1)/2]);
    }
    cout << res << endl;
    return 0;
}