ac1278.pas

这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码

{$Q-,R-}
program tju1278;
const
  maxn=200;
  inf=65535;
var
  buy,eat:array[1..maxn]of byte;
  sum:array[0..maxn]of word;
  time:array[boolean,0..sqr(maxn)]of word;
  n,i,j,t1,t2:longint;
  b1,b2:boolean;
procedure qsort(s,t:byte);
  var
    p,i,j,tbuy,teat:byte;
  begin
    if s>=t then exit;
    p:=s+random(t-s+1);
    tbuy:=buy[p];buy[p]:=buy[s];teat:=eat[p];eat[p]:=eat[s];
    i:=s;j:=t;
    repeat
      while (i<j) and (eat[j]<=teat) do dec(j);
      if i=j then break;buy[i]:=buy[j];eat[i]:=eat[j];inc(i);
      while (i<j) and (eat[i]>=teat) do inc(i);
      if i=j then break;buy[j]:=buy[i];eat[j]:=eat[i];dec(j);
    until i=j;
    buy[i]:=tbuy;eat[i]:=teat;
    qsort(s,i-1);
    qsort(i+1,t);
  end;
begin
  repeat
    read(n);
    for i:=1 to n do read(buy[i],eat[i]);
    qsort(1,n);
    for i:=1 to n do sum[i]:=sum[i-1]+buy[i];

    fillchar(time[false],sizeof(time[false]),255);
    time[false,0]:=0;
    for i:=1 to n do begin
      b1:=odd(i);b2:=not b1;
      fillchar(time[b1],sizeof(time[b1]),255);
      for j:=0 to sum[i] shr 1 do begin
        //Join 1st queue
        if (j>=buy[i]) and (time[b2,j-buy[i]]<inf) then begin
          t1:=j+eat[i];
          if time[b2,j-buy[i]]>t1 then t1:=time[b2,j-buy[i]];
        end
        else
          t1:=inf;
        //Join 2st queue
        if time[b2,j]<inf then begin
          t2:=sum[i]-j+eat[i];
          if time[b2,j]>t2 then t2:=time[b2,j];
        end
        else
          t2:=inf;
        if t1<t2 then time[b1,j]:=t1 else time[b1,j]:=t2;
      end;
      for j:=sum[i] shr 1+1 to sum[i] do
        time[b1,j]:=time[b1,sum[i]-j];
    end;

    i:=inf;
    for j:=0 to sum[n] do
      if time[b1,j]<i then i:=time[b1,j];
    writeln(i);
  until seekeof;
end.