小木棍

https://loj.ac/problem/10020

题目描述

  有(N)根小木棍，他们有各自的长度，若它们能拼成整数多的(len)长的木棍，求(len)的最小值。

思路

  从题目上看，一个显然的思路是我们可以暴力从小到大枚举(len)，用(dfs)看能否拼成这么多木棍。不过裸的(dfs)肯定T飞了，我们尝试进行优化。

  首先从可行性方面进行优化，我们提出五种剪枝：

  (①)一根长木棍用处肯定比用几根短木棍拼成相同长度的作用小，所以我们可以把木棍从大到小排序。

  (②)我们按照这个顺序依次处理每一根木棍，那么显然到第(i)个木棍时，只能从(i+1)开始寻找，因为前面的都已用过。

  (③)判断当前木棍的长度能否拼成(len)长木棍，不能就直接返回。

  (④)找到答案立刻返回。

  我们再从最优性方面做出两种剪枝：

  (⑤)设所有木棍长为(sum),那我们枚举的(len)一定能整除(sum)。

  (⑥len)一定大于等于剩余木棍中最长的。

代码

#include<bits/stdc++.h>
using namespace std;

int sum,len,cnt,a[70],nxt[70],n;
bool f,used[70];
void dfs(int k,int rest,int s)
{
//    cout<<k<<' '<<rest<<' '<<s<<endl;
    if(f)return ;
    if(s==sum/len){f=1;return ;}
    if(rest==0) 
    {
        int i=cnt;
        while(used[i]&&i<=n)i++;
        used[i]=1;
        dfs(i,len-a[i],s+1);
        used[i]=0;
        if(f)return ;
    }
    
    int l=k+1,r=n;
    while(l<r)
    {
        int mid=l+r>>1;
        if(a[mid]>rest)l=mid+1;
        else r=mid;
    }
    
    for(int i=l;i<=n;i++)
    {
        if(used[i]||a[i]>rest)continue ;
        used[i]=1;
        dfs(i,rest-a[i],s);
        used[i]=0;
        if(a[i]==rest||rest==len)return ;
        i=nxt[i];
        if(i==n)return ;
    } 
}

bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),sum+=a[i];
    sort(a+1,a+n+1,cmp);
    cnt=1;
    while(a[cnt]>50)sum-=a[cnt++];
    nxt[n]=n;
    for(int i=n-1;i>=cnt;i--)
        if(a[i]==a[i+1])nxt[i]=nxt[i+1];
        else nxt[i]=i;
    for(len=a[cnt];len<=sum;len++)
        if(sum%len==0)
        {
            used[cnt]=1;
            dfs(cnt,len-a[cnt],1);
            used[cnt]=0;
            if(f){printf("%d",len);break ;}
        }
}