有n个小朋友坐成一圈，每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。

 

1号小朋友给了n号小朋友x1颗糖

2号小朋友给了1号小朋友x2颗糖

……

那么ans=|x1|+|x2|+|x3|……+|xn|

设ai-average=ci;

a1+x2-x1=average

变形得

x1-c1=x2;

x2-c2=x3=>x1-c1-c2=x3

……

x1-(c1+c2+……+cn)=x1;

那么

ans=|x1-c1|+|x1-(c1+c2)|+|x1-(c1+c2+c3)|+……|x1|

这不就是个中位数水题吗

看我一发A了它

#include
     
      #define re return#define ll long long #define inc(i,l,r) for(int i=l;i<=r;++i)using namespace std;template
      
       inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;} ll n,T,a[1000005],b[1000005]; int main(){    freopen("in.txt","r",stdin);        ll average=0;    rd(n);    inc(i,1,n)    {        rd(a[i]);        average+=a[i];    }        average/=n;        inc(i,1,n)    b[i]=b[i-1]+a[i]-average;        sort(b+1,b+n+1);        ll mid=b[(n+1)>>1],ans=0;            inc(i,1,(n+1)>>1)    ans+=mid-b[i];        inc(i,((n+1)>>1)+1,n)    ans+=b[i]-mid;        printf("%lld",ans);    re 0;}