未透过的1011——堆栈方式

未通过的1011——堆栈方式

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		Scanner s = new Scanner(System.in);
		while (s.hasNextInt()) {
			// 获得长度
			int count = s.nextInt();
			if (count == 0) {
				break;
			}

			int[] nums = new int[count];

			// 获得数组、和
			int sum = 0;
			for (int i = 0; i < count; i++) {
				int num = s.nextInt();
				sum += num;
				nums[i] = num;
			}
			// 排序
			Arrays.sort(nums);

			// 最大值
			int max = nums[count - 1];

			// 遍历可能的结果
			for (int i : getList(sum)) {
				if (max <= i) {
					if (exec(nums, i, sum)) {
						break;
					}
				}
			}

		}

		s.close();

	}

	public boolean exec(int[] nums, int l, int sum) {
		// 数组长度
		int size = nums.length;
		// 可变总长
		int s = l;
		// 堆栈
		Stack<Integer> stack = new Stack<Integer>();
		// 标记
		boolean[] flags = new boolean[size];
		// 初始化i
		int i = size - 1;

		while (true) {

			for (; i >= 0; i--) {
				// 如果剩余可用数之和不够，pass
				if (!isEnough(nums, flags, i, s)) {
					break;
				}
				// 如果当前数不可用，pass
				if (flags[i]) {
					continue;
				}
				int n = nums[i];
				// 如果大于和，pass
				if (n > s) {
					continue;
				}
				// 如果跟上一个可用数一样，pass
				if (i + 1 < size && n == nums[i + 1] && !flags[i + 1]) {
					continue;
				}
				// 标记已用
				flags[i] = true;
				// 进栈
				stack.push(i);
				// 从和中减掉
				s -= n;
				if (s == 0) {
					sum -= l;
					// 判断是否全部用尽
					if (sum == 0) {
						System.out.println(l);
						return true;
					} else {
						// 再次轮回匹配剩余的可用数
						i = size - 1;
						s = l;
					}
				}
			}
			// 可用数用尽，当前匹配也没成功
			// 恢复最后的数
			int top = stack.pop();
			flags[top] = false;
			s += nums[top];
			if (s == l) {
				sum += l;
				if (!stack.isEmpty()) {
					top = stack.pop();
					flags[top] = false;
					s = nums[top];
				}
			}
			// 如果是边缘，恢复倒数第二个数
			if (top == 0) {
				top = stack.pop();
				flags[top] = false;
				s += nums[top];
			}
			// 如果弹出的数是栈中最后一个，匹配失败
			if (top == size - 1) {
				return false;
			}
			// 从下一个可用数开始
			i = top - 1;
		}
	}

	// 判断剩余可用数之和是否够
	public boolean isEnough(int[] nums, boolean[] flags, int begin, int sum) {
		for (int i = begin; i >= 0; i--) {
			if (!flags[i]) {
				sum -= nums[i];
				if (sum <= 0) {
					return true;
				}
			}
		}
		return false;
	}

	// 获得可能的结果List
	public List<Integer> getList(int n) {
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 1; i <= Math.sqrt(n); i++) {
			if (n % i == 0) {
				list.add(i);
				if (i * i != n) {
					list.add(n / i);
				}
			}
		}
		Collections.sort(list);
		return list;
	}
}