#include <stdio.h>
#include <stdlib.h>

#define	SMX	100

#define	MAX(x, y)	((x) > (y)) ? (x) : (y)

int	N, len, stick[SMX];

int cmp(const void *a, const void *b) {
	return((*(int *)b) - (*(int *)a));
}

int can_alloc(int n) {
	int	i, j, l = len, s = 0, bs = 0, fin, tot = 0, sublen = len / n, alloc[SMX], step[SMX], total[SMX], begin[SMX];

	for(i = 0; i < N; alloc[i] = step[i] = total[i] = begin[i] = 0, i++);

	while(l) {
		for(i = step[s], j = 0, tot = total[s], fin = 0; i < N; i++) {
			if(tot == 0)
				begin[bs] = s;

			if(alloc[i] == 0 && stick[i] <= sublen - tot) {
				alloc[i] = 1;
				tot += stick[i];
				step[s] = i;
				total[s] = tot;
				l -= stick[i];
				s++;
				step[s] = 0;
				total[s] = 0;
			}

			if(tot == sublen) {
				begin[++bs] = 0;
				fin = 1;
				break;
			}

		}

		if(!fin) {
			if(s <= 0)
				return(0);
			else
				while(--s) {
					l += stick[step[s]];
					total[s] -= stick[step[s]];
					alloc[step[s]] = 0;

					if(s == begin[bs])
						continue;
					else {
						if(s < begin[bs])
							begin[bs--] = 0;

						for(j = step[s] + 1; j < N && stick[j] == stick[step[s]]; j++);

						if(j >= N)
							continue;
						else
							step[s] = j;
						break;
					}
				}

		}
	}

	return(1);
}

int main() {
	int	n, max;

	while(1) {
		fscanf(stdin, "%d", &N);

		if(N == 0)
			break;

		for(n = 0, len = 0, max = 0; n < N; n++) {
			fscanf(stdin, "%d", &stick[n]);
			len += stick[n];
			max = MAX(max, stick[n]);
		}

		qsort(stick, N, sizeof(int), cmp);

		for(n = N / 2 + 1; n > 1; n--) {
			if(len % n > 0 || len / n < max)
				continue;

			if(can_alloc(n)) {
				printf("%d\n", len / n);
				break;
			}
		}

		if(n == 1)
			printf("%d\n", len);
	}
}

• Re:我提交了15次了。。。现在TLE…… (63) winboycool 2007-04-21 16:28:32