program poj1011     ;
type aa=array[1..64]of integer;
var i,j,k,n,long,last,last2:integer;
    sm:aa;
    find,ok:boolean;
    map:array[1..64]of integer;
    b:array[1..64]of boolean;
procedure qsort(var a:aa;l,r:integer);//快排
var i,j,t:integer;
begin
    if l<r then
    begin
        t:=a[l];
        i:=l;
        j:=r;
        repeat
            while (i<j)and (t>=a[j]) do j:=j-1;
            if i<j then
            begin
                a[i]:=a[j];
                i:=i+1;
            end;
            while (i<j)and(t<=a[i]) do i:=i+1;
            if i<j then
            begin
                a[j]:=a[i];
                j:=j-1;
            end;
        until i>=j;
        a[i]:=t;
        qsort(a,l,i-1);
        qsort(a,i+1,r);
    end;
end;
procedure  put(num,x:integer);
var i,j,k:integer;
begin
    if  (find) then  exit;
    if num=n then begin find:=true; exit;end
    else
    if map[x]=long then begin put(num,x+1);ok:=true;end
    else
    if map[x]=0 then
    begin
       i:=2;
       while ((not b[i])or(sm[i]=last))and(i<=n) do  i:=i+1;
       if i=n+1 then exit;
       b[i]:=false;
       map[x]:=map[x]+sm[i];
       put(num+1,x);
       map[x]:=map[x]-sm[i];
       b[i]:=true;
       last:=sm[i];
    end
    else
    begin
       for i:=2 to n do
       if ((map[x]+sm[i])<=long)and(b[i])and(ok)and(sm[i]<>last2) then
       begin
           map[x]:=map[x]+sm[i];
           b[i]:=false;
           put(num+1,x);
           map[x]:=map[x]-sm[i];
           b[i]:=true;last2:=sm[i];
       end;
    end
end;
begin
    readln(n);
    while n<>0 do
    begin
        fillchar(sm,sizeof(sm),0);
        k:=0;
        for i:=1 to n do begin read(sm[i]); k:=k+sm[i];end//此处k记录短棍子长度和，sm记录各根棍子的长度
        readln;
        qsort(sm,1,n);
        find:=false;
        long:=sm[1];
        while not find do
        begin
           long:=long+1;//long是记录当前长棍子的长度
           if (k mod long)=0 then
           begin
               fillchar(b,sizeof(b),true);//b用来记录某根段棍子是否可用，true为可用
               fillchar(map,sizeof(map),0);//map是记录每根长棍子已用长度
               ok:=true;
               last:=0;
               last2:=0;
               map[1]:=sm[1];
               b[1]:=false;
               put(1,1);
           end;
        end;
        writeln(long);
        readln(n)
    end
end.

• Re:我的程序能秒杀前面的那组BT数据，但仍然超时 (0) liangzijie2010 2012-08-13 11:16:39