您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

167. 木棒

乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过50 个长度单位。

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

请你设计一个程序,帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式

输入包含多组数据,每组数据包括两行。

第一行是一个不超过 64 的整数,表示砍断之后共有多少节木棍。

第二行是截断以后,所得到的各节木棍的长度。

在最后一组数据之后,是一个零。

输出格式

为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。

数据范围

数据保证每一节木棍的长度均不大于 50。

输入样例:

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

输出样例:

6
5

分析:这道题如何剪枝很重要,我先把输入的数组从大到小排了序,然后从1开始用函数dfs遍历每一个答案, 若其中一个可以就不用往后遍历了,dfs函数中我剪的枝有两个,su是此刻该木棒中已经有的长度,cnt是分配的每个木棒原本的长度,一个是若此刻a[i]+su==cnt但却返回false,那证明后面的数组更不符合了,因为后面的数组都小于等于a[i],小的数可以拼更多的东西,因此用a[i]拼当前的应该是最佳方案,但依然不合适,因此可以直接返回false了,还有一种就是该木棒中放第一个木棒就返回false,那之后的必然都不合适,可以直接返回false;

if(su+a[i]==cnt||!su)return false;

还有一个小技巧,如果当前a[i]不合适,那之后与a[i]相等的数组也可以不用遍历了

int j=i;
while(j<=n&&a[j]==a[i])j++;
i=j-1;

整体代码如下:

#include <bits/stdc++.h>

using namespace std;

int a[65],st[65];
int n,s,cnt;
bool dfs(int id,int su,int sta)
{
    if(su==cnt) id++,su=0,sta=1;
    if(id*cnt==s) return true;
    
    for(int i=sta;i<=n;i++)
    {
        if(st[i])continue;
        if(su+a[i]>cnt)continue;
        st[i]=1;
        if(dfs(id,su+a[i],i+1))return true;
        st[i]=0;
        if(su+a[i]==cnt||!su)return false;
        int j=i;
        while(j<=n&&a[j]==a[i])j++;
        i=j-1;
    }
    return false;
}

int main()
{
    while(cin>>n&&n)
    {
        s=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            s+=a[i];
        }
        sort(a+1,a+n+1);
        reverse(a+1,a+n+1);
        cnt=a[1]-1;
        fill(st+1,st+n+1,0);
        while(cnt<=s)
        {
            if(s%(++cnt)) continue;
            if(dfs(0,0,1))
            {
                cout<<cnt<<endl;
                break;
            }
        }
    }
    return 0;
}

 

 


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进