2293 - L2125 的题解

回去原题
#认为是一道数学题,以样例为例,算法如下:
用A、B、C、D、E顺时针排列依次表示第1个书架至第5个书架且顺次向其后面的书架搬动 x1,x2,x3,x4,x5本书,依题意得      
7+x1-x2=11+x2-x3=3+x3-x4=14+x4-x5=15+x5-x=10    
得 x2=x1-3,x3=x1-2,x4=x1-9,x5=x1-5  
本题要求
y=│x1│+│x2│+│x3│+│x4│+│x5│      
=│x1│+│x1-3│+│x1-2│+│x1-9│+│x1-5│的最小值。
又因为题目保证书架个数为奇数个,所以由绝对值几何意义知,当x1=3时,y有最小值12, 此时有x2=0,x3=1,x4=-6,x5=-2。
即从第1个书架搬动3本书到第2个书架,从第3个书架搬动1本书到第4个书架,从第5个书架搬动6本书到第4个书架,从第1个书架搬动2本书到第5个书架,这样搬动的书本总本数最小,且为12本。
此外只要注意数据很大要用int64,就可以做出此题,代码实现如下:
var
  s:int64;
  n,i:longint;
  a,b:array[1..5000001] of int64;

procedure qsort(l,r:longint);
var
  i,j:longint;
  mid,t:int64;
begin
  i:=l;
  j:=r;
  mid:=a[random(r-l+1)+l];
  repeat
    while a[i]<mid do i:=i+1;
    while a[j]>mid do j:=j-1;
    if i<=j then
      begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
        i:=i+1;
        j:=j-1;
      end;
  until i>j;
  if i<r then qsort(i,r);
  if l<j then qsort(l,j);
end;

begin
  assign(input,'book.in');
  reset(input);
  assign(output,'book.out');
  rewrite(output);
  randomize;
  readln(n);
  s:=0;
  for i:=1 to n do
    begin
      read(b[i]);
      s:=s+b[i];
    end;
  s:=s div n;
  for i:=2 to n do a[i]:=a[i-1]+b[i]-s;
  b:=a;
  qsort(1,n);
  s:=-a[(n+1) div 2];
  for i:=1 to n do b[i]:=b[i]+s;
  s:=0;
  for i:=1 to n do s:=s+abs(b[i]);
  a[1]:=-b[n];
  for i:=2 to n do a[i]:=-b[i-1];
  writeln(s);
  for i:=1 to n do writeln(a[i],' ',b[i]);
  close(input);
  close(output);
end.