一道ACM题，求代码。。。只要代码，不要在网上复制粘贴，要原创，codeblocks运行没有任何问

Question

一道ACM题，求代码。。。只要代码，不要在网上复制粘贴，要原创，codeblocks运行没有任何问题的代码。
Description
George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input
The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output
The output should contains the smallest possible length of original sticks, one per line.

Sample Input
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
Sample Output
6
5

Answer 1

你好，这道题的意思大概是找几个树枝刚好用完拼起来的树枝长度都一样且最短。首先树枝的最小长度肯定不能比这些折断后的最长树枝的长度小，所以我们可以以折断后最长树枝的长度为起点设变量 i 。

算法思想是这样的：按长度从大到小排序折断后得树枝放到List中，循环List，用 i 减去第一个值(也就是最大值)得到差值a，如果a为0则 a = i继续,如果 a 不等于0，则判断a是否存在List中，如果不存在则a = i 继续循环，如果存在的话我们可以去计算一下还有多少个树枝，如果树枝刚好用完了，则表明 i 值就是最小长度，如果不是则 i++ ,继续。

代码如下：

static void Main(string[] args)
{
            List<List<int>> lengthList = new List<List<int>>();
            List<int> lengths = null;
            Console.WriteLine("请输入截断后的棍子数(输入0结束)：");
            int parts = Convert.ToInt32(Console.ReadLine());
            while (parts != 0)
            {
                lengths = new List<int>();
                Console.WriteLine("请输入这些棍子的长度：");
                for (int i = 0; i < parts; i++)
                {
                    ConsoleKeyInfo keyInfo = Console.ReadKey(false);
                    Console.Write(" ");
                    lengths.Add(Convert.ToInt32(keyInfo.KeyChar.ToString()));
                }
                lengthList.Add(lengths);
                Console.WriteLine("\n请输入截断后的棍子数(输入0结束)：");
                parts = Convert.ToInt32(Console.ReadLine());
            }
            foreach (List<int> le in lengthList)
            {
                le.Sort();// æŽ’序
                for (int i = le[le.Count - 1]; i < 10000; i++)// ä»ŽæŠ˜æ–­åŽæœ€é•¿æ ‘枝的长度开始，这里的10000按需求
                {
                    List<int> temp = new List<int>(le);// æ‹·è´ä¸€ä¸ªæ–°çš„list,以免后面的remove操作改变了原数据
                    if (test(i, temp))
                    {
                        Console.WriteLine("结果为：\n {0}",i);
                        break;
                    }
                }
            }


            Console.ReadLine();
        }

        public static bool test(int a, List<int> temp)
        {
            bool bl = false;
            int b = a;
            for (int i = temp.Count - 1; i >= 0; i--)// ä»Žå¤§åˆ°å°å¾ªçŽ¯
            {
                b = b - temp[i];// å‡åŽ»å½“前值
                temp.RemoveAt(i);// æŠŠå½“前值从List中移除
                if (b == 0)// i=折断后最长树枝的长度处理
                {
                    b = a;
                    continue;
                }
                if (temp.Contains(b))// å¦‚果包含所得的差值
                {
                    temp.Remove(b);// æŠŠæ‰€å¾—的差值从List中移除
                    i--;           // åæ ‡å‡1
                    if (temp.Count == 0)//如果最后一个所得的差值刚好存在List中，移除后List中元素数量变为0
                    {
                        bl = true;// å½“前的a(也就是传进来的i)即为最小长度
                    }
                    b = a;
                }
            }

            return bl;
        }
}

运行结果：

大致算法应该就是这样了，如果大家有更好的算法的话，希望都贴出来，总之希望能帮到你吧，还望采纳

Answer 2

#include <stdio.h> #include <string.h> #include <stdlib.h> int len[64],n,minlen,get; int used[64]; void quickSort(int a[],int s,int m) {    int i,j,t;     if(s<m){        i=s,j=m+1;         while(1){            while(i+1<64&&a[++i]>a[s]);             while(j-1>-1&&a[--j]<a[s]);             if(i>=j)break;             t=a[i],a[i]=a[j],a[j]=t;        }         t=a[s],a[s]=a[j],a[j]=t;         quickSort(a,s,j-1);         quickSort(a,j+1,m);}} //现在的长度，已用的根数，剩余根数 int dfs(int nowlen,int nowget,int cnt) {     if(cnt>=n) return 0;      if(get==nowget) return 1;      int i;      int f=0;      if(nowlen==0) f=1;      for(i=cnt;i<n;i++)      {if(!used[i]){if(len[i]+nowlen==minlen){                 used[i]=1;                 if(dfs(0,nowget+1,nowget))return 1;                 used[i] = 0;                 return 0;}             else if(len[i]+nowlen<minlen)             {   used[i]=1;                 if(dfs(nowlen+len[i],nowget,i+1))return 1;                 used[i]=0;                 if(f) return 0;                 while(i+1<n&&len[i]==len[i+1]) i++;}}}     return 0; } int main() {    int i, tollen;     while(scanf("%d",&n)!=EOF&&n!=0)     {   tollen = 0;         int j=0,p;         for(i=0;i<n;i++)         {   scanf("%d",&p);             if(p<=50)             {   len[j]=p;                 tollen+=len[j];                 j++;}}         n=j;//总段数         quickSort(len,0,n-1);//将棍子按大到小排列         for(minlen=len[0];;minlen++)         {   if(tollen%minlen) continue;             for(i=0;i<64;i++)                 used[i]=0;//重置所有棍子             get=tollen/minlen;             if(dfs(0,0,0))             { printf("%d\n",minlen);             break;}}}     return 0; }