阿里巴巴校园招聘题目

一、题目：有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1，求使所有人获得均等糖果的最小代价。

  假设每个人都要给左右分糖果（可以大于等于或者小于0），a1分给an的糖果数为k，则可以得到以下的信息：

                  a1              a2                      　    a3 　　　　　　　　  an-1 　　　　　　　　　　　　 an

当前数目：a1-k          a2 　　　　　　　　 a3 　　　　　　　　  an-1 　　　　　　　　　　　　 an+k

所需代价：|a1-k-ave| |a1+a2-k-2*ave| |a1+a2+a3-k-3*ave| ....|a1+..+a(n-1)-k-(n-1)*ave|  |k|

以sum[i]表示从a1加到ai减掉i*ave的和值，这以上可以化简为

总代价 = |s1-k|+|s2-k|+...+|s(n-1)-k|+|k|

不难看出：当k为s1...s(n-1)中的中位数的时候，所需的代价最小

---

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int X = 1000005;

long sum[X],a[X];

long n;

long Abs(long x){

    return max(x,-x);

}

int main(){

     while(cin>>n){

        long x;

        long tot = 0;

        for(int i=1;i<=n;i++){

            cin>>a[i];

            tot += a[i];

        }

        long ave = tot/n;

        for(int i=1;i<n;i++)

            sum[i] = a[i]+sum[i-1]-ave;

        sort(sum+1,sum+n);

        long mid = sum[n/2];

        long ans = Abs(mid);

        for(int i=1;i<n;i++)

            ans += Abs(sum[i]-mid);//每一步的代价

        cout<<ans<<endl;

    }

    return 0;//输出最小代价

}