题目描述
乔治拿来一组等长的木棒,将它们随机地砍断,使得每一节木棍的长度都不超过50个长度单位。
然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。
请你设计一个程序,帮助乔治计算木棒的可能最小长度。
每一节木棍的长度都用大于零的整数表示。
样例
输入样例:
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例:
6
5
算法1
(暴力枚举) $O(n^2)$
优化:
1.从大到小枚举木棍。
2.跳过相同的木棍
3.如果第一个木棍失败,则以后肯定也会失败,所以直接跳过dfs
4.如果最后一根木棍失败,则跳出整个dfs,同理。
时间复杂度
参考文献
C++ 代码
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 70;
int n;
int sum, length;
int sticks[N];
bool st[N];
bool dfs(int u, int cur, int start)//u表示枚举到第几块木棒(长的),cur表示当前木棒拼了多长, start 表示当前枚举到第几根木棍(短)
{
if (u * length == sum) return true;
if (cur == length) return dfs(u + 1, 0, 0);
for (int i = start; i < n; i ++ )
{
if (st[i]) continue;
int l = sticks[i];
if (cur + l <= length)
{
st[i] = true;
if (dfs(u, cur + l, i + 1)) return true;
st[i] = false;
// 剪枝3 如果是第一个木棒失败,则一定失败
if (!cur) return false;
// 剪枝4 如果是最后一个木棒失败,则一定失败
if (cur + l == length) return false;
// 剪枝2 跳过相同木棒
int j = i;
while (j < n && sticks[j] == l) j ++ ;
i = j - 1;
}
}
return false;
}
int main()
{
while (cin >> n, n)
{
sum = 0, length = 0;
memset(st, false, sizeof st);
for (int i = 0; i < n; i ++ )
{
cin >> sticks[i];
if (sticks[i] > 50) {
st[i] = true;
continue;
}
sum += sticks[i];
length = max(length, sticks[i]);
}
// 剪枝:优化搜索顺序
sort(sticks, sticks + n);
reverse(sticks, sticks + n);
// for (int i = 0; i < n; i ++ )
// if (sticks[i] > 50)
// st[i] = true;
while (true)
{
if (sum % length == 0 && dfs(0, 0, 0))
{
cout << length << endl;
break;
}
length ++ ;
}
}
return 0;
}