题解 P1368 【均分纸牌（加强版）】

66666a · 2017-02-09 10:25:54 · 题解

已获得原作者转载同意（讨论里那个）

正文：

首先我们假设平均数为sum1。那么对于第1个人，我们假设他给第N个人K个糖果，第2个人给1，第3个人给2,第n个人给第n-1个人那么对于第1个人给完n，第2个人给完1，第一个人不会再改变糖果数了，所以应该是sum1那么第一个人原来是a1，给n之后是a1-k，代价是k，第2个人给1，使1的糖果数是sum1，所以应该给sum1-a1+k个，代价是abs(sum1+k-a1)=abs(a1-k-sum1)，那么第2个人变成了a2+a1-k-sum1个第3个人需要给2个人sum1-a2-a1+k+sum1=2*sum1-a1-a2+k个，那么代价是abs(2*sum1-a1-a2+k)=abs(a1+a2-k-2*sum1)，以此类推第n个人给第n-1个人，代价应为abs((a1+a2+……+an-1)-k-(n-1)*sum1)，那么第一个人给第n个人的代价k可以看成abs((a1+a2+……+an)-k-n*sum1)，所以我们设b[i]=Σ(a[j])-i*sum1 j<=i那么max=Σ(b[i]-k)，那么b[i]是定值，和k无关，我们可以求出来，就是求max的最小值了，那么k应该是b[i]数组中的中位数，可以使max最小我们要找的就是sum的中位数，快排下就好了

p代码

var
  n:longint;
  a,b:array[0..1000010] of int64;
  i:longint;
  sum1:int64;
  max,k:int64;
procedure qk(l,r:longint);
var
  i,j,m:longint;
  t:int64;
begin
  i:=l; j:=r; m:=b[(i+j) div 2];
  while i<j do
    begin
      while b[i]<m do inc(i);
      while b[j]>m do dec(j);
      if i<=j then 
      begin
        t:=b[i]; b[i]:=b[j]; b[j]:=t;
        inc(i); dec(j);
      end;
    end;
  if i<r then qk(i,r);
  if j>l then qk(l,j);
end;
begin
  readln(n);
  for i:=1 to n do 
    begin
      read(a[i]);
      b[i]:=b[i-1]+a[i];
    end;
  sum1:=b[n] div n;
  for i:=1 to n do b[i]:=b[i]-i*sum1;
  qk(1,n);
  k:=b[(1+n) div 2];
  for i:=1 to n do max:=max+abs(b[i]-k);
  writeln(max);
end.