import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Scanner;
public class Main {

	/**
	 * @param args
	 */
	static int[] stick;
	static int n;
	static int max;
	static int min;
	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		while(n != 0){
			stick = new int[n];
			int sum = 0;
			max = -1;
			min = 51;
			for(int i = 0; i < n; i++){
				stick[i] = in.nextInt();
				sum += stick[i];
				max = Math.max(max, stick[i]);
				min = Math.min(min, stick[i]);
			}
			System.out.println("不是吧");//请看这个地方，这样都TLE
			Arrays.sort(stick);
			for(int average = 1; average <= sum; average++){
				if(sum % average == 0){
					if(max > average || (max < average && max + min > average))
						continue;
					int[] state = new int[sum / average];
					if(ok(state, sum / average, 0, average)){
						System.out.println(average);
						break;
					}
				}
			}
			n = in.nextInt();
		}
	}
	public static boolean ok(int[] state, int count, int index, int average){
		boolean res = false;
		if(index == n)
			return true;
		for(int i = 0; i < count; i++){
			if(state[i] + stick[index] <= average){
				if(state[i] + min > average)
					return false;
				state[i] += stick[index];
				if(ok(state, count, index + 1, average)){
					res = true;
					break;
				}
				else{
					state[i] -= stick[index];
				}
			}
			if(state[i] == 0){
				break;
			}
		}
		return res;
	}
}

• 先判 时间， 再判 结果 (1739) semonteer 2006-03-27 20:48:28
  • Re:先判 时间， 再判 结果 (26) Iambitious 2006-03-27 22:05:28
    • 可以减 (48) semonteer 2006-03-27 22:10:14
      • Re:可以减 (52) Iambitious 2006-03-28 09:46:04
        • Re:可以减 (15) Iambitious 2006-03-28 09:46:17
      • Re:可以减 (56) sunhongkao 2009-08-07 19:42:19