小木棒

玉竹君 · 2019-01-12 17:28:34 · 题解

这是我三个小时做出来的！不是因为难思考！是因为细节！！！哭了！

首先我们还是运用的是深搜的方法，里面我加上了二分法。 这个题的主要思路我觉得其实很简单 分析一下这道题目，我们不难发现，答案是有范围的，就是最小是最长那根小木棒，最大是所有小木棒之和！（划重点，敲黑板） 我们用一个next数组标记，如果有两根一样的木棒，两根的情况是一样的，所以我们算一个就好了。 每一次我们判定完一根木棒后，我们要把它标记，这样我们就不会重复计算了! 还有在输入的时候我们可以进行判定，因为题目中给出了，所以只要该根超过了50我们就可以直接把它拿出来了！ 我们设一个函数（nume表示这个是第几根木棒；last是上一个木棒的编号；rest是这根大木棒还剩下多少要拼） 我们不难发现，其实从大到小排比从小到大简单，因为几根小的肯定会比一根大的灵活，我们这样思考这根问题就很简单的可以将这根木棒拼出来。

我们就先写个小代码，叫二分的小可爱：(就是这个小可爱不会让你的代码炸掉哦）

int l=last+1,r=coUnt,mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if(a[mid]<=rest)
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }

然后我们判定一下这个小木棒的组成，m代表的是我们这种情况分出的大木棒根数，裁枝：如果等于我们假设的了，我们就可以停止了。 下面就是我的代码了：

#include<bits/stdc++.h>
using namespace std;
int a[70] ;
int n , m , sum , next[70],len,coUnt;
bool gg[70],pass;
bool comp (int a,int b){return a>b;}
void jj(int num , int last , int rest)
{
    int i;

    int l=last+1,r=coUnt,mid;
    while(l<r)
    {
        mid=(l+r)/2;
        if(a[mid]<=rest)
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    if(!rest)
    { 
        if(num==m)
        {
            pass=1;
            return ;
        }
        for(i=1;i<=coUnt;i++)
        { 
            if(!gg[i]) break;
        } 
        gg[i]=1;
        jj(num+1,i,len-a[i]);
        gg[i]=0;
        if(pass)
        {
            return;
        } 
    }
    for(i=l;i<=coUnt;i++)
    {
        if(!gg[i])
        {
            gg[i]=1;
            jj(num,i,rest-a[i]);
            gg[i]=0;
            if(pass)
            return ;
            if(rest==a[i]||rest==len)
            return ;
            i=next[i];
            if(i==coUnt)
            return ;
        }
    }
}
int main()
{
    int llo;
    scanf("%d", &n );
    for(int i = 1 ; i <= n ; i++)
    {
        scanf("%d",&llo);
        if(llo>50) continue;
        a[++coUnt]=llo;     
        sum+=llo;
    }
    sort(a+1,a+coUnt+1,comp);
    next[coUnt]=coUnt;
    for(int i=coUnt-1;i>0;i--)
    {
        if(a[i]!=a[i+1])
            next[i]=i;
        else
        next[i]=next[i+1];
    }
    for(len=a[1];len<=sum/2;len++)
    { 
        if(sum%len!=0) 
        continue; 
        pass=0;
        gg[1]=1;
        m=sum/len; 
        jj(1,1,len-a[1]);
        gg[1]=0;
        if(pass)
        {
            printf("%d\n",len);
            return 0;
        }       
    }
    printf("%d\n",sum);
    return 0;

}