试题算法训练小木棍

蔚落 2024-03-31 08:45 89阅读 0赞

## 试题 算法训练 小木棍 ##

资源限制  
内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s  
问题描述  
　　RJ有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 50。现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。  
　　给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。  
输入格式  
　　第一行为一个单独的整数 N 表示看过以后的小木柜的总数，其中 N<=60；

第二行为 N 个用空个隔开的正整数，表示 N 跟小木棍的长度。。  
输出格式  
　　输出文件仅一行，表示要求的原始木棍的最小可能长度。  
样例输入  
9  
5 2 1 5 2 1 5 2 1  
样例输出  
6  
**提交代码**:

#include<stdio.h>
    #include<algorithm>
    using namespace std;
    int n;
    int a[100],book[100];
    bool cmp(int x,int y)
    {
        
        return x>y;
    }
    int len,cnt;
    int dfs(int num,int lasti,int l)
    {
        
        //num为拼好的个数，lasti为上一个的编号，l为已拼成的长度
        if(num==cnt+1) //表示拼成了cnt根小木棍且小木棍没有剩余，符合题目所求
            return 1;
        if(l==len)//拼成一个len长度num+1
            return dfs(num+1,1,0);
        for(int i=lasti; i<=n; i++)//剪枝，当用木棍i拼接最初的木棍时，可以从第i+1后的木棍开始搜索，因为排序，前面的木棍已经用过了
        {
        
            if(!book[i]&&l+a[i]<=len)  //保证当前长度加上正在选的小木棍长度不大于len，如果大于len就是没有小木棍可以拼成len长度的小木棍，不符合条件
            {
        
                book[i]=1;
                if(dfs(num,i+1,l+a[i]))
                    return 1;
                book[i]=0;//深搜搜索后要取消标记
                if(l==0||l+a[i]==len)//剪枝，找不到能拼成len长度的木棍
                    return 0;
                while(a[i]==a[i+1])//去重剪枝 相同长度的不符合条件的则不需再搜索
                    i++;
            }
        }
        return 0;
    }
    int main()
    {
        
        scanf("%d",&n);
        int s=0;
        //排序，最初小木棍的长度一定大于等于砍断后的小木棍的最大的长度，并且小于所有小木棍的长度之和
        for(int i=1; i<=n; i++)
        {
        
            scanf("%d",&a[i]);
            s+=a[i];
        }
        sort(a+1,a+1+n,cmp);
        //所有小木棍的长度之和为s，则拼成若干根的小木棍的长度一定能被s整除，否则就拼不成，因为拼成的小木棍必须是整数根
        for(len=a[1]; len<=s; len++)
        {
        
            if(s%len==0)
            {
        
                cnt=s/len;
                if(dfs(1,1,0))
                    break;
            }
        }
        printf("%d\n",len);
        return 0;
    }