题目描述
乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过 50 个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序,帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
输入格式
输入包含多组数据,每组数据包括两行。
第一行是一个不超过 64 的整数,表示砍断之后共有多少节木棍。
第二行是截断以后,所得到的各节木棍的长度。
在最后一组数据之后,是一个零。
输出格式
为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。
数据范围
数据保证每一节木棍的长度均不大于 50。
样例
输入样例:
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例:
6
5
算法1
个人理解写在注释里面了, 有错误的地方麻烦各位大佬指正(拜谢!)
C++ 代码
#include<iostream>
#include<bits/stdc++.h>
using namespace std ;
const int N = 70 ;
int p[N] ;
bool aq[N] ;
int a , n , m ;
int length ,sum = 0 ;
bool dfs(int x , int s , int st)
{
if(x * length == sum ) return true ;
if(s == length ) return dfs(x + 1 , 0 , 0) ;
for(int i = st ; i < n ; i ++){
if(aq[i]) continue ;
if(s + p[i] > length) continue ;
aq[i] = 1 ;
if(dfs(x , s + p[i] , i+1)) return true ;
aq[i] = 0 ;
// 剪枝 :如果当前第一个 木棍放进去都不行, 那后面所有 排列都不可能凑出答案
/*
比如 : 1 3 5 4 当前是 4
假设前面 x 根棍已经摆好了
如果当前(x+1)第一个放 4 , 往下搜的时候发现不合法,就直接返回false ;
反证法 : 如果当前第一个没放 4 ,最后该方案成功了
说明 后面的棍子中肯定 有某个地方放了 4
假设摆放 的 方式 是 1 4 5
则我们 可以调换一下顺序 变成 4 1 5 ,让 4 在最前面 !
再将这一行和 前面的 (x+1)行 互换一下位置 !
就变成了 在第 (x+1 )行 的第一个位置摆放了 4 ,最后方案合法
与假设(如果(x+1)行的第一个木棍摆放 4 ,该方案不合法) 矛盾 ,所以 得证 ;
*/
if(!s) return false ;
// 剪枝 : 如果当前摆放最后一根木棍长度 刚好满足length ;
// 最后方案不合法,则直接返回false ;
if(s + p[i] == length) return false ;
int j = i ;
while(j < n && p[i] == p[j]) j ++ ;
i = j -1 ;
}
return false ;
}
int main(){
ios::sync_with_stdio(0) ;
cin.tie(0) ;
while( cin >> n , n )
{
memset( aq , 0 , sizeof aq) ;
sum = 0 ;
for(int i = 0 ;i < n ; i ++) {
cin >> p[i] ;
sum += p[i] ;
}
// 优化搜索顺序
sort(p , p + n ) ;
reverse(p , p+ n) ;
length = 1 ;
while(true)
{
if( sum %length == 0 && dfs(0 , 0 , 0) )
break ;
length ++ ;
}
cout << length << '\n' ;
}
return 0 ;
}