题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1045

我们假设每一个小朋友的代价为$x[i]$，每一次都从前面一个小朋友那里拿，这种贪心跟纸牌均摊很像，想一想很容易理解。

设最后每个小朋友能得到$ave$个糖果，所以有$a[i]+x[i]-x[i+1]=ave$。

写出每一个形如这样的式子，可以消元得到$x[n]=x[1]+(n-1)*ave-sum[n-1]$。

我们令$c[i]=(i-1)*ave-sum[i-1]$，则我们最后所求为$Ans=\{\sum_{i=1}^n|x[1]-c[i]|\}_{min}$。

把$x[1]$和$c[i]$看成数轴上的点，可以证明当$x[1]$为$c[i]$的中位数时，取得$Ans$值。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 typedef long long ll; 7 int inline readint(){ 8     int Num;char ch; 9     while((ch=getchar())<'0'||ch>'9') ;Num=ch-'0';10     while((ch=getchar())>='0'&&ch<='9') Num=Num*10+ch-'0';11     return Num;12 }13 int N;14 ll a[1000010],b[1000010],ave;15 int main(){16     N=readint();17     ll sum=0;18     for(int i=1;i<=N;i++){19         a[i]=readint();20         sum+=a[i];21     }22     ave=sum/N;23     sum=0;24     for(int i=1;i<=N;i++){25         b[i]=ave*(i-1)-sum;26         sum+=a[i];27     }28     sort(b+1,b+1+N);29     int mid=N+1>>1;30     ll ans=0;31     for(int i=1;i<=N;i++) ans+=abs(b[mid]-b[i]);32     printf("%lld\n",ans);33     return 0;34 }