bzoj 1045糖果传递 数学贪心

首先我们假设平均数为ave

那么对于第1个人，我们假设他给第N个人K个糖果，第2个人给1，第3个人给2,第n个人给第n-1个人

那么对于第1个人给完n，第2个人给完1，第一个人不会再改变糖果数了，所以应该是ave

那么第一个人原来是a1，给n之后是a1-k，代价是k，第2个人给1，使1的糖果数是ave，所以应该

给ave-a1+k个，代价是abs(ave+k-a1)=abs(a1-k-ave)，那么第2个人变成了a2+a1-k-ave个

第3个人需要给2个人ave-a2-a1+k+ave=2*ave-a1-a2+k个，那么代价是

abs(2*ave-a1-a2+k)=abs(a1+a2-k-2*ave)，以此类推

第n个人给第n-1个人，代价应为abs((a1+a2+……+an-1)-k-(n-1)*ave)，那么第一个人给第n个人

的代价k可以看成abs((a1+a2+……+an)-k-n*ave)，所以我们设sum[i]=Σ(a[j])-i*ave    j<=i

那么ans=Σ(sum[i]-k)，那么sum[i]是定值，和k无关，我们可以求出来，就是求ans的最小值了，

那么k应该是sum[i]数组中的中位数，可以使ans最小

我们要找的就是sum的中位数，快排下就好了

//By BLADEVIL

var

    n                    :longint;

    a, sum                :array[..] of int64;

    i                    :longint;

    ave                    :int64;

    ans, k                :int64;

procedure swap(var a,b:int64);

var

    c                    :int64;

begin

    c:=a; a:=b; b:=c;

end;

procedure qs(low,high:longint);

var

    i, j, xx            :longint;

begin

    i:=low; j:=high; xx:=sum[(i+j) div ];

    while i<j do

    begin

        while sum[i]<xx do inc(i);

        while sum[j]>xx do dec(j);

        if i<=j then

        begin

            swap(sum[i],sum[j]);

            inc(i); dec(j);

        end;

    end;

    if i<high then qs(i,high);

    if j>low then qs(low,j);

end;

begin

    read(n);

    for i:= to n do read(a[i]);

    for i:= to n do sum[i]:=sum[i-]+a[i];

    ave:=sum[n] div n;

    for i:= to n do sum[i]:=sum[i]-i*ave;

    qs(,n);

    k:=sum[(+n) div ];

    for i:= to n do ans:=ans+abs(sum[i]-k);

    writeln(ans);

end.