program Q1011;
  type       
    s=array[1..100]of longint;
  var       
    a:s;
    i,n,total,try:longint;
  procedure paiXu(var a:s;n:longint);
    var 
      i,j,k,temp:longint;
    begin
      for i:=1 to n-1 do
        begin
          k:=i;for j:=i+1 to n do if a[k]<a[j] then k:=j;
          if k<>i then begin temp:=a[i];a[i]:=a[k];a[k]:=temp end
        end
    end;
  function findOne(var a:s;n,length:longint):boolean; 
    var  
      i,temp:longint;
    begin
      if length=0 then begin findOne:=true;exit end; {拼接完成,返回}
      for i:=1 to n do
        if (a[i]<>0)and(a[i]<=length) then 
          begin 
            temp:=a[i];a[i]:=0;
            if findOne(a,n,length-a[i]) then {拼接完成,继续返回}
              begin findOne:=true;exit end;
            a[i]:=temp {拼接失败，数据还原}
          end;
      findOne:=false {拼接失败,返回}                                     
    end;
  function check(a:s;n,length,count:longint):boolean; 
    var         {a为传值，不影响下一次check}
      i:longint; 
    begin
      for i:=1 to count do
        if not findOne(a,n,length)
          then begin check:=false;exit end;
      check:=true
    end;
  begin
    readln(n);
    repeat
      total:=0;
      for i:=1 to n do
        begin
          read(a[i]);total:=total+a[i]
        end; 
      readln;
      paiXu(a,n); {由贪心原理，从大到小排序，拼接时先拼长的}
      try:=a[1];
      repeat
        while total mod try<>0 do 
          try:=try+1;
        if check(a,n,try,total mod try) then break;
        try:=try+1
      until false;
      writeln(try);
      readln(n)
    until n=0
  end.

• 我还只学了Pascal呢，这题用随机化做很爽 (0) JiangLY 2005-05-05 00:03:27
  • Re:我还只学了Pascal呢，这题用随机化做很爽 (7) zdker 2005-05-05 01:34:04
    • Re:我还只学了Pascal呢，这题用随机化做很爽 (11) jiangly 2005-05-05 11:06:23
      • 你觉得这题能用贪心吗? (0) JiangLY 2005-05-05 11:06:49
  • 请问这题怎么随机化比较好？ (0) cubic 2005-08-04 22:05:10
    • 纯DFS+剪枝可以么？ (0) sunmoonstar_love 2005-08-06 20:27:03
      • ft~~~~~~~这两天晕，问些没用的问题 (0) sunmoonstar_love 2005-08-06 20:31:41