fence8.pas

Magio牛的usaco源代码

{
ID:maigoak1
PROG:fence8
}

program fence8;
const
  maxb=50;
  maxr=1023;
var
  fin,fout:text;
  board:array[1..maxb]of integer;
  rail:array[0..maxr]of integer;
  boards,rails,min,i,j,l,r,t:integer;
  sum,sum1:longint;
procedure exchange(var x,y:integer);
  var
    t:integer;
  begin
    t:=x;x:=y;y:=t;
  end;
procedure out(x:integer);
  begin
    assign(fout,'fence8.out');
    rewrite(fout);
    writeln(fout,x);
    close(fout);
    halt;
  end;
function ok(x:integer):boolean;
  procedure try(x,start:integer);
    var
      i:integer;
    begin
      if x=0 then begin ok:=true;exit;end;
      for i:=start to boards do
        if board[i]=rail[x] then begin
          board[i]:=0;
          if rail[x]=rail[x-1] then try(x-1,i+1) else try(x-1,1);
          board[i]:=rail[x];
          exit;
        end;
      for i:=start to boards do
        if board[i]>rail[x] then begin
          board[i]:=board[i]-rail[x];
          if rail[x]=rail[x-1] then try(x-1,i) else try(x-1,1);
          board[i]:=board[i]+rail[x];
          if ok then exit;
        end;
    end;
  begin
    ok:=false;
    try(x,1);
  end;
begin
  assign(fin,'fence8.in');
  reset(fin);
  readln(fin,boards);
  sum:=0;
  for i:=1 to boards do begin
    readln(fin,board[i]);
    sum:=sum+board[i];
  end;
  readln(fin,rails);
  for i:=1 to rails do
    readln(fin,rail[i]);
  close(fin);

  for i:=1 to boards-1 do
    for j:=i+1 to boards do
      if board[i]>board[j] then exchange(board[i],board[j]);
  sum1:=0;
  for i:=1 to rails do begin
    min:=maxint;
    for j:=i to rails do
      if rail[j]<min then begin min:=rail[j];t:=j;end;
    exchange(rail[i],rail[t]);
    sum1:=sum1+rail[i];
    if sum1>sum then begin
      rails:=i-1;
      break;
    end;
  end;

  l:=0;r:=rails;
  repeat
    t:=(l+r) div 2;
    if ok(t) then
      if t=rails then
        out(rails)
      else
        if ok(t+1) then
          l:=t+1
        else
          out(t)
    else
      r:=t-1;
  until false;
end.