1432：糖果传递

1432：糖果传递

（ybt 太毒瘤了，这个题输出答案要用cout   ,  printf不行）

洛谷： P2512 [HAOI2008]糖果传递

 

题解

每人每次传递一个糖果代价为1

每人每次传递一个糖果代价为1

每人每次传递一个糖果代价为1

 

 

 

代码

#include<bits/stdc++.h>

using namespace std;

int n,a[1000001],c[1000001];
long long sum=0,anv,ans;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
    anv=sum/n;   //最终小朋友手里的糖数 
    
    c[1]=a[1]-anv+a[n];    //左边的小朋友传给右边（他们坐成了一个环） 
    for(int i=2;i<=n;i++)
       c[i]=a[i]-anv+c[i-1];
    
    sort(c+1,c+n+1);   //每个人要传递多少 
    
    int mid=c[n/2+1];    //传递的中位数 
    for(int i=1;i<=n;i++)  
      ans+=fabs(c[i]-mid);   //只需要传递到中位数就好了，多了太浪费 
    
    printf("%ld",ans); 
    
}