题目分析

乔治将一些相同长度的小木棍随意砍成若干段，每段长度不超过 50。现在给出所有小段的长度，要求找出原始木棍的最小可能长度。原始木棍的长度必须满足：

  1. 不小于所有小段中的最大长度。
  2. 是所有小段总长度的约数（因为总长度是原始长度的整数倍）。
  3. 能够用所有小段恰好拼成若干根原始木棍（无剩余）。

解题思路

  1. 数据预处理：

    • 读入小段数量 n 和各小段长度。
    • 计算总长度 sum 和最大长度 max_len。
    • 将小段按长度从大到小排序（有助于剪枝优化）。

  2. 枚举原始长度：

    • 原始长度 L 的范围是 [max_len, sum]，且 sum % L == 0。
    • 为高效查找最小 L，先收集所有满足条件的约数并排序（从小到大）。

  3. 深度优先搜索 (DFS) 验证：

    • 对于每个候选 L，计算需要拼成的原始木棍数量 k = sum / L。
    • 使用 DFS 尝试将所有小段拼成 k 根长度为 L 的木棍。
    • 关键剪枝优化：
      • 固定首段：第一根木棍必须包含最长的小段（排序后首元素），减少搜索分支。
      • 跳过相同长度：在同一位置尝试失败后，跳过后续相同长度的小段。
      • 首段失败剪枝：若当前木棍的第一段尝试失败，则整个方案失败（因为该段必须作为某根木棍的开头）。
      • 末段失败剪枝：若当前小段恰好补全木棍但失败，则整个方案失败（因为最后一段必须匹配）。

  4. DFS 状态设计：

    • stick_count：已成功拼接的原始木棍数量。
    • cur_len：当前正在拼接的木棍已累积长度。
    • start：当前木棍下一段的起始搜索位置（避免重复组合）。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 70;
int n, a[MAXN], sum, max_len;
bool used[MAXN];
int L, k; // 全局变量：当前尝试的原始长度L，需要拼成的根数k

// DFS验证能否拼成k根长度为L的原始木棍
bool dfs(int stick_count, int cur_len, int start) {
    // 所有木棍已拼成
    if (stick_count == k) {
        return true;
    }
    // 当前木棍已拼满，开始拼下一根
    if (cur_len == L) {
        return dfs(stick_count + 1, 0, 0);
    }

    int last = 0; // 记录上一次尝试的小段长度，用于跳过相同长度
    for (int i = start; i < n; i++) {
        if (used[i]) continue; // 跳过已使用的小段
        if (a[i] == last) continue; // 剪枝：跳过相同长度
        if (cur_len + a[i] > L) continue; // 超长跳过

        used[i] = true;
        last = a[i]; // 记录当前长度

        bool next;
        // 当前小段恰好补全木棍
        if (cur_len + a[i] == L) {
            next = dfs(stick_count + 1, 0, 0);
        } else {
            // 继续拼当前木棍，从下一段开始搜索
            next = dfs(stick_count, cur_len + a[i], i + 1);
        }

        if (next) return true; // 成功则返回

        // 回溯
        used[i] = false;

        // 剪枝1：当前是木棍的第一段，失败则整体失败
        if (cur_len == 0) {
            return false;
        }
        // 剪枝2：当前小段是木棍的最后一段，失败则整体失败
        if (cur_len + a[i] == L) {
            return false;
        }
    }
    return false;
}

int main() {
    cin >> n;
    sum = 0;
    max_len = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
        if (a[i] > max_len) max_len = a[i];
    }
    // 从大到小排序
    sort(a, a + n, greater<int>());

    // 收集所有可能的原始长度L（sum的约数且>=max_len）
    vector<int> divisors;
    for (int i = max_len; i <= sum; i++) {
        if (sum % i == 0) {
            int k_temp = sum / i;
            if (k_temp > n) continue; // 根数不可能大于小段数
            divisors.push_back(i);
        }
    }
    sort(divisors.begin(), divisors.end()); // 从小到大排序

    // 枚举每个候选L
    for (int i = 0; i < divisors.size(); i++) {
        L = divisors[i];
        k = sum / L;

        memset(used, false, sizeof(used));
        // 固定最长小段作为第一根木棍的首段
        used[0] = true;
        if (dfs(0, a[0], 1)) {
            cout << L << endl;
            return 0;
        }
        used[0] = false;
    }

    // 理论上不会执行到此处（L=sum时一定成功）
    cout << sum << endl;
    return 0;
}

DFS 验证：

  • 固定首段：强制将最长小段作为第一根木棍的开头，减少搜索空间。
  • 剪枝策略：
    • 跳过相同长度小段（避免重复尝试）。
    • 首段失败则整体失败（该段必须作为某根开头）。
    • 末段失败则整体失败（最后一段必须精确匹配）。

复杂度分析

1. 时间复杂度

  • 最坏情况：O(D × 2n)
    • D：总长度 sum 的有效约数个数（满足 L ≥ max_len 且 sum % L == 0）
      • 由于 sum ≤ 64 × 50 = 3200，约数个数 D ≤ 60（3200 的约数共 30 个）
    • 2n：DFS 搜索树的理论上界（n 个小木棍的子集组合）

2. 空间复杂度

  • O(n)：
    • used[] 数组：O(n) 存储小木棍使用状态
    • DFS 递归栈：最大深度为 n（每层处理一个小木棍）
    • 其他辅助变量：O(1)
  • 无额外数据结构：未使用记忆化（状态空间过大），所有优化通过剪枝实现