问题描述

乔治拿来一组等长的木棒，将它们随机地裁断，使得每一节木棒的长度都不超过50 个

长度单位。然后他又想把这些木棒恢复到裁截前的状态，但忘记了初始时有多少木棒以及木

棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棒的长度

都用大于零的整数表示。

输入数据

由多个案例组成，每个案例包括两行。第一行是一个不超过64 的整数，表示裁截之后

共有多少节木棒。第二行是经过裁截后，所得到的各节木棒的长度。在最后一个案例之后，

是零。

输出要求

为每个案例，分别输出木棒的可能最小长度，每个案例占一行。

输入样例

9

5 2 1 5 2 1 5 2 1

4

1 2 3 4

0

输出样例

6

5

　　一看到这道题目感觉有些熟悉，后来才发现是一年零两个月前我曾经遇到过道题。但是当时没弄明白。呵呵。 这次一开始看到这道题的时候还是没有思路。还是看了解析后才有思路。

　　木棍组合问题，因为不知道原始长度、每根被截成了几节。所以要怎么才能组合起来呢。我们可以知道这些小木棍要组成原始的长度，那么他们的原始长度必须比最大那一节大或者等于，于是可以排序，qsort。然后就可以去对每个长度去尝试。因为不知道每次要几根木棍才能构成原始长度，那么我们就只能有搜索的方法。这是必须传递参数每次还剩多少长度（nLeftLength）才能构成一根木棍，还有一个是总的木棍还剩多少根（nLeftSticks）。通过这两个参数是否等于零可以判断出是否能组成一组相等的木棍。在拼接木棍的时候，还应该考虑当一根木棍拼接成功后，必须把剩余的长度（nLeftLength）给重新置成原始长度，继续搜索，直到把所有的木棍用完。搜索的时候为了避免重复利用，还要开辟个数组used[MAX]来标示是否已经被使用。当然我们还要考虑每次递归搜索的时候，行不通的时候，要回溯。继续下一种情况。

#include 
     
      #include 
      
       #define MAX 64int sticks[MAX];int used[MAX];int nStickNum,len;int cmp(const void *elemA, const void *elemB);int concatenate(int nLeftSticks,int nLeftLength);int main(){    int i,nSum;    int nStickLength;while(scanf("%d",&nStickNum) && nStickNum !=0){    for(i = 0; i < nStickNum; i++)    {        scanf("%d",&sticks[i]);    }    qsort(sticks,nStickNum,sizeof(int),cmp);    //sum    nSum=0;    for(i = 0; i < nStickNum; i++)    {        nSum+=sticks[i];        used[i] = 0;    }    nStickLength = sticks[0];   //the length of stick    for(len = nStickLength; len <= nSum/2; len++)    {        if(nSum % len == 0 && concatenate(nStickNum,nStickLength))        {            printf("%d\n",len);            break;        }    }}    return 0;}int cmp(const void *elemA, const void *elemB){    return *(int *)elemB - *(int *)elemA;}int concatenate(int nLeftSticks,int nLeftLength){     int i;    if(nLeftSticks == 0 && nLeftLength ==0) return 1;    else if(nLeftLength == 0) nLeftLength = len;        for(i = 0; i < nStickNum; i++)    {        if( !used[i] && nLeftLength >= sticks[i])        {            used[i] = 1;            nLeftLength -=sticks[i];            if(concatenate(nLeftSticks-1,nLeftLength)) return 1;            used[i] = 0;            nLeftLength +=sticks[i];            if(sticks[i] == nLeftLength || nLeftLength == len) break;        }    }    return 0;}2013/5/19  19:19