🧠 解题思路
1️⃣ 问题转化
假设原始竹简的标准长度为 len，
那么我们需要判断：能否把所有片段分组，使得每组的和恰好为 len。
这是一个典型的 分组搜索问题（类似于木棒拼接问题）。
但由于数据较多（n ≤ 50），暴力搜索需要优化。
2️⃣ 关键思路：剪枝 + 回溯
步骤如下：
- 计算片段总长度
sum。 - 枚举可能的竹简标准长度
len：len必须是sum的约数；- 且
len >= max(a_i)。
- 对每个可能的
len，用回溯搜索判断是否能分组成功。
剪枝技巧
- 将片段按长度从大到小排序（优先使用大块能极大降低分支数）。
- 当当前片段无法放入某篇竹简时，可以跳过相同长度的片段。
- 若当前篇竹简的第一个片段都无法放入，则直接回溯。
- 若找到一种拼法，则立即输出。
3️⃣ 时间复杂度
虽然是回溯搜索，但在强剪枝下可以高效运行（n ≤ 50）。
💻 C++ 参考代码
#include <bits/stdc++.h>
using namespace std;
int n, total;
int a[70];
bool used[70];
int target, cnt;
bool dfs(int stick, int cur, int idx) {
if (stick > cnt) return true; // 所有竹简拼完
if (cur == target)
return dfs(stick + 1, 0, 0); // 当前竹简拼好，开始下一篇
int fail = 0;
for (int i = idx; i < n; ++i) {
if (used[i]) continue;
if (cur + a[i] > target || a[i] == fail) continue;
used[i] = true;
if (dfs(stick, cur + a[i], i + 1)) return true;
used[i] = false;
fail = a[i]; // 剪枝：避免重复尝试同样长度的片段
if (cur == 0 || cur + a[i] == target) return false;
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
int sum = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i];
sum += a[i];
}
sort(a, a + n, greater<int>());
for (target = a[0]; target <= sum; ++target) {
if (sum % target != 0) continue; // 必须能整除
cnt = sum / target;
memset(used, false, sizeof(used));
if (dfs(1, 0, 0)) {
cout << target << "\n";
return 0;
}
}
return 0;
}
共 1 条回复
太强了%%%%