AcWing 167. 木棒

题意：

有一堆木棒他们是从几根等长木棍切出来的，现在知道这堆木棒分别的长度，问你重组成几根等长的木棍且要求该等长最短的长度。

思路：

这题一开始看的时候我还以为是二分长度不断取小，结果想半天不会。 这题其实是一道搜索剪枝，涉及到的剪枝其实还挺巧妙的，首先我们可以对木棒根据长度先排个序从大的开始往后用，如果遍历到他的时候用不上，在组这根木棍也就用不上了，木棒之间除了长度是没有差别的，所以我们只需在意长度大小和数量多少即可，这一波分析完TMD不就是做个桶排序吗。让后我们从最大的木棒长度枚举到所有木棒长度之和，这里涉及可行性剪枝。搜索过程中的剪枝见代码。

AC代码：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int max_n=1e6+10; int t[max_n]; int sum,maxn,len; void init() { sum = 0,maxn = 0,len = 0; memset(t,0,sizeof(t)); } bool dfs(int remain,int now,int pos) { if(remain == 0) return true;//所有木棍都拼完了返回正确 if(now == len) return dfs(remain-1,0,maxn);//当前拼接成功一根继续拼下一根 for(int i=pos;i>=0;i--) {//当前用的最大长度往下枚举 if(t[i]&&now+i<=len) { t[i]--;//用去一根 if(dfs(remain,now+i,i)) return true; t[i]++;//失败回溯 if(now==0||now+i==len) return false;//失败原因是在拼好一根的情况下该答案长度错误直接返回false } } } int main() { int n; while(cin>>n&&n) { init(); for(int i=1,x;i<=n;i++) { cin>>x; t[x]++; maxn = max(x,maxn); sum+=x; } for(int i=maxn;i<=sum;i++) { if(sum<i*2) {//可行性剪枝 cout<<sum<<endl; break; } if(sum%i) continue; len = i; if(dfs(sum/i,0,maxn)) { cout<<len<<endl; break; } } } }