[USACO精选] 第三章 排序

#9 重排干草 2014-02-12

QAQ这么快居然开学了，这么来说时间越来越少了…开学第二天，作业不多，赶紧抽出时间把这道想了很久的题给搞定……真的想了很久，其实看了解题也想了很久，我觉得我等数学弱渣肯定自己推论不到这个地步…我觉得我晚上还得再想想这东西…

p[i]=b[i]-a[i]+p[i-1]为i接收到的草，ans=sigma(p[i])，由于p[i+1]-p[i]确定，所以p[n]=abs(某个定值+k)，k是第一个坑要收到的草，k=0-p数组的中位数时取到答案。（好难TvT…至今晕）

program usaco_;

var a,b:array[..] of integer;

    p:array[..] of longint;

    ave,n,i:longint;

    ans:qword;

procedure qsort(l,r:longint);

var i,j,mid,temp:longint;

begin

  i:=l;j:=r;mid:=p[(l+r) div ];

  repeat

    while p[i]<mid do inc(i);

    while p[j]>mid do dec(j);

    if i<=j then

      begin

        temp:=p[i];p[i]:=p[j];p[j]:=temp;

        inc(i);dec(j);

      end;

  until i>j;

  if i<r then qsort(i,r);

  if j>l then qsort(l,j);

end;

begin

  readln(n);

  for i:= to n do

    begin

      readln(a[i],b[i]);

      p[i]:=b[i]-a[i]+p[i-];

    end;

  qsort(,n);

  ave:=-p[n div ];

  for i:= to n do

    ans:=ans+abs(p[i]+ave);

  writeln(ans);

end.

重排干草

话说有人说这题是BZOJ1045，默默地打开AC率为0的BZOJ账号，改了下程序，过了我BZOJ第一题…话说一开始没看清楚数据范围RE了一次，然后莫名明明是RE给我报了WA我又莫名WA了很多次…总之最后还是过了。纪念下。

program bzoj1045;

var a:array[..] of longint;

    p:array[..] of longint;

    n,i,b,ave:longint;

    sum,ans:qword;

procedure qsort(l,r:longint);

var i,j,mid,temp:longint;

begin

  i:=l;j:=r;mid:=p[(l+r) div ];

  repeat

    while p[i]<mid do inc(i);

    while p[j]>mid do dec(j);

    if i<=j then

      begin

        temp:=p[i];p[i]:=p[j];p[j]:=temp;

        inc(i);dec(j);

      end;

  until i>j;

  if i<r then qsort(i,r);

  if j>l then qsort(l,j);

end;

begin

  readln(n);

  for i:= to n do

    begin

      readln(a[i]);

      sum:=sum+a[i];

    end;

  b:=sum div n;

  for i:= to n do

    p[i]:=b-a[i]+p[i-];

  qsort(,n);

  ave:=p[n div ];

  for i:= to n do

    ans:=ans+abs(p[i]-ave);

  writeln(ans);

end.

糖果传递

思路什么的最重要了，数学渣渣的撸主泪奔去了…