122. 糖果传递

贪心

贪心的题一般代码比较短，但是思维量比较大。
这个题可以说是一个完全的数学题。

得到绿色的公式后，这个题就和

货仓选址

一样了。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
ll a[N];
ll c[N];
int n;
int main()
{
    ll sum = 0;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum+=a[i];
    ll avg = sum / n;
    for(int i=n;i>=2;i--)
    {
        c[i] = c[i+1] + avg - a[i];
    }
  //  c[1] = 0;
    sort(c+1,c+1+n);
    
    int k = n/2 + 1; //从1~n的中位数是n/2+1    1~5的中位数：3
    ll res = 0;
    for(int i=1;i<=n;i++) res +=abs( c[i] - c[k]);
    printf("%lld",res);
}