题目描述
乔治拿来一组等长的木棒,将它们随机地裁断,使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态,但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序,帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。
Input
输入包含多组数据,每组数据包括两行。第一行是一个不超过64的整数,表示砍断之后共有多少节木棍。第二行是截断以后,所得到的各节木棍的长度。在最后一组数据之后,是一个零。
Output
为每组数据,分别输出原始木棒的可能最小长度,每组数据占一行。
样例
Sample
Input Output
9
5 2 1 5 2 1 5 2 1 5
4
1 2 3 4 6
0
算法1
(DFS) $O(n^2)$
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a(64);
vector<int> visit(64);
int num;
int len = 1;
bool dfs(int used_num, int now_len, int now_index) {
if (now_len == len) {
return (used_num == num) ? true : dfs(used_num, 0, 0);
}
if (now_len == 0) {
while (visit[now_index] == 1) now_index++;
visit[now_index] = 1;
bool result = dfs(used_num + 1, a[now_index], now_index + 1);
visit[now_index] = 0;
return result;
} else {
for (int i = now_index; i < num; i++) {
if ((visit[i] == 0) && (now_len + a[i]) <= len) {
if (visit[i - 1] == 0 && a[i] == a[i - 1]) {
continue;
}
visit[i] = 1;
bool result = dfs(used_num + 1, now_len + a[i], i + 1);
visit[i] = 0;
if (result) return true;
}
}
}
return false;
}
bool cmp(int x, int y) {
return x > y;
}
int main() {
while (cin >> num) {
if (num == 0) {
break;
}
int sum = 0, max_len = 0;
for (int i = 0; i < num; i++) {
cin >> a[i];
sum += a[i];
max_len = max(max_len, a[i]);
}
sort(a.begin(), a.begin() + num, cmp);
for (len = max_len; len < sum; len++) {
if (sum % len == 0 && dfs(0, 0, 0)) {
break;
}
}
cout << len << endl;
}
return 0;
}
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla