POJ： 1011 Sticks
POJ： 1011问题描述
乔治拿来一组等长的木棒，将它们随机地裁断，使得每一节木棒的长度都不超过 50 个
长度单位。然后他又想把这些木棒恢复到裁截前的状态，但忘记了初始时有多少木棒以及木
棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棒的长度
都用大于零的整数表示。
输入数据
由多个案例组成，每个案例包括两行。第一行是一个不超过 64 的整数，表示裁截之后
共有多少节木棒。第二行是经过裁截后，所得到的各节木棒的长度。在最后一个案例之后，
是零。
输出要求
为每个案例，分别输出木棒的可能最小长度，每个案例占一行。
输入样例
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例
6
5
C代码：
#include <stdio.h>#include <stdlib.h>int arry;int used;//标当前木棍有没有被使用记int comp(const void *a, const void *b){ int c = (*(int *)a)-(*(int *)b); if( c >= 0 )return -1; else return 1;}int judge(int n, int unused, int left, int len){ int i; if( (unused==0) && (left==0) )return 1; if( left == 0 )left = len;//当前木棍拼装完成后进行下一根木棍的拼装 for( i = 0; i < n; i++ ) { if( used ) continue; if( arry > left ) continue; used = 1; if( judge(n, unused-1, left-arry, len) )return 1; used = 0; if( (arry==left) || (left==len) )break; //当前木棍是最后一根或者是开始位置会导致出错 } return 0;}int main(){ int i, j; int n, sum, len; while( scanf("%d", &n) && n ) { sum = 0; for( i = 0; i < n; i++ ) { scanf("%d", &arry); sum += arry; used = 0; } qsort(arry, n, sizeof(int), comp); for( i = arry; ; i++ ) { if( sum%i == 0 ) { if( judge(n, n, 0, i) == 1 ) { printf("%d\n", i); break; } } } } return 0;}
页:
[1]