企业官网建设流程全解析

题目描述

乔治将一些等长的木棍随机切割，直到所有木棍部分的长度都不超过505050单位。现在他忘记了原始木棍的数量和长度，想将这些木棍部分重新拼成原始等长木棍。请编写程序，计算出原始木棍可能的最小长度。

所有长度都是大于000的整数。

输入格式

输入文件包含多个数据块，每个数据块两行：

• 第一行：切割后的木棍部分数量nnn
• 第二行：nnn个木棍部分的长度，用空格分隔
• 最后一行以0表示输入结束

输出格式

对于每个数据块，输出一行，包含原始木棍的最小可能长度。

样例输入

9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0

样例输出

6 5

样例解释

• 第一组：999根木棍部分，总长度5+2+1+5+2+1+5+2+1=245+2+1+5+2+1+5+2+1 = 245+2+1+5+2+1+5+2+1=24，原始木棍长度为666时，可以拼成444根(5+1,5+1,5+1,2+2+2)(5+1, 5+1, 5+1, 2+2+2)(5+1,5+1,5+1,2+2+2)
• 第二组：444根木棍部分，总长度1+2+3+4=101+2+3+4 = 101+2+3+4=10，原始木棍长度为555时，可以拼成222根(1+4,2+3)(1+4, 2+3)(1+4,2+3)

题目分析

问题的本质

这是一个经典的木棍拼接问题，属于“划分问题”的变种。给定若干小木棍（切割后的部分），要求将它们拼成若干根等长的大木棍，求大木棍可能的最小长度。

等价表述：将nnn个数划分成若干个和相等的子集，求这个和的最小可能值。

数学约束

设木棍部分的总长度为S=∑stick[i]S = \sum \text{stick}[i]S=∑stick[i]，原始木棍长度为LLL，原始木棍数量为k=S/Lk = S / Lk=S/L。由于kkk必须是整数，因此LLL必须是SSS的约数。

此外，LLL至少等于最长木棍部分的长度（因为一根原始木棍至少要能容纳最长的部分）。

因此，可能的LLL取值范围是：
max⁡(stick)≤L≤S \max(\text{stick}) \leq L \leq Smax(stick)≤L≤S
且LLL必须是SSS的约数。

直接枚举的可行性

nnn的最大值未在题目中明确给出，但根据木棍部分长度≤50\leq 50≤50和常见的数据范围，nnn可能达到646464甚至更大。直接枚举所有划分方案（子集划分）是指数级的，不可行。必须使用搜索 + 剪枝。

解题思路

步骤一：排序与预处理

为了优化搜索，将木棍部分按从大到小排序。原因：

• 大的木棍更难匹配，先处理大木棍可以尽早发现不可行的情况
• 便于剪枝：如果当前剩余空间连最小的木棍都放不下，可以直接回溯

步骤二：枚举可能的原始长度

从L=stick[0]L = \text{stick}[0]L=stick[0]（最长部分）开始，依次检查每个SSS的约数。只要找到第一个可行的LLL，它就是最小的可能长度（因为从小到大枚举）。

步骤三：深度优先搜索

对于给定的候选长度goal，需要判断能否将所有的木棍部分拼成若干根长度为goal的大木棍。

搜索状态：

• sum：当前正在拼接的大木棍已经累加的长度
• idx：当前考虑的木棍部分的起始索引
• count：已经成功拼好的大木棍数量

目标：count == total，其中total = S / goal。

步骤四：剪枝策略

这是本题的关键。有效的剪枝可以大幅减少搜索空间：

1. 整除剪枝：goal必须能整除总长度S，否则跳过

2. 重复元素剪枝：如果当前木棍长度与前一个相同，且前一个未被使用，则跳过当前。因为相同的长度尝试顺序会重复产生相同的组合。

   if(i&&!used[i-1]&&stick[i]==stick[i-1])continue;

3. 组合完成剪枝：如果sum + stick[i] == goal，说明当前大木棍恰好拼满。此时：

   • 标记使用该木棍
   • 递归拼下一根大木棍（dfs(0, 0, count + 1)）
   • 如果递归失败，返回false（因为当前大木棍的最后一根木棍必须被使用，如果它导致后续失败，则当前方案不可行）

4. 起始失败剪枝：如果sum == 0（即正在拼一根新的大木棍），且当前选择的木棍导致失败，则直接返回false。因为这是该大木棍的第一根木棍，如果它不行，任何其他木棍作为第一根也不会成功（由于降序排序，当前是剩余可用的最大木棍）。

5. 空间不足剪枝：如果sum + stick[i] < goal，尝试继续拼接。但要注意，如果当前是空木棍（sum == 0）且选择了当前木棍后失败，则直接返回false。

步骤五：搜索框架

booldfs(intsum,intidx,intcount){if(count==total)returntrue;// 所有大木棍都拼好了for(inti=idx;i<n;i++){if(used[i])continue;// 剪枝2：跳过重复的未使用元素if(i>0&&!used[i-1]&&stick[i]==stick[i-1])continue;if(sum+stick[i]==goal){used[i]=1;if(dfs(0,0,count+1))returntrue;used[i]=0;returnfalse;// 剪枝3：最后一根木棍失败}elseif(sum+stick[i]<goal){used[i]=1;if(dfs(sum+stick[i],i+1,count))returntrue;used[i]=0;if(sum==0)returnfalse;// 剪枝4：第一根木棍失败}}returnfalse;}

算法复杂度分析

时间复杂度

• 最坏情况下，搜索空间是指数级的
• 但通过多种剪枝策略，实际运行效率很高
• n=64n = 64n=64时，UVa 评测时间约为0.1000.1000.100秒

空间复杂度

• 存储木棍长度：O(n)O(n)O(n)
• 标记数组：O(n)O(n)O(n)
• 总空间复杂度：O(n)O(n)O(n)

正确性证明

引理 1：原始木棍长度LLL必须是总长度SSS的约数。

证明：每根原始木棍长度为LLL，共有kkk根，则S=k×LS = k \times LS=k×L，因此LLL是SSS的约数。□\square□

引理 2：降序排序 + 优先尝试大木棍不会遗漏可行解。

证明：如果存在一个可行解，将其中每根大木棍内的木棍部分按任意顺序排列，都可以通过重排得到降序搜索过程中访问到的某种顺序。因此，降序搜索是完备的。□\square□

引理 3：剪枝策略是安全的（不会剪掉可行解）。

证明：

• 重复元素剪枝：由于排序后相同长度的木棍等价，跳过重复不会丢失解
• 最后一根木棍失败剪枝：如果当前大木棍的最后一根木棍（恰好填满）导致后续失败，则任何其他组合填满当前大木棍也会失败（因为最后一根木棍是唯一的）
• 第一根木棍失败剪枝：如果当前大木棍的第一根木棍导致失败，则任何其他木棍作为第一根也一定会失败（因为当前是剩余木棍中最长的，更长的已经试过不行，更短的只会留下更难以匹配的剩余空间）
  □\square□

参考代码

// Sticks// UVa ID: 307// Verdict: Accepted// Submission Date: 2017-01-06// UVa Run Time: 0.100s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intstick[105];// 木棍部分的长度intused[105];// 标记是否已使用intn;// 木棍部分的数量intgoal;// 当前尝试的原始木棍长度inttotal;// 原始木棍的数量// 深度优先搜索// sum: 当前正在拼接的大木棍已累加的长度// idx: 当前考虑的木棍部分的起始索引// count: 已经成功拼好的大木棍数量booldfs(intsum,intidx,intcount){// 所有大木棍都拼好了if(count==total)returntrue;for(inti=idx;i<n;i++){// 如果当前木棍已使用，跳过if(used[i])continue;// 剪枝1：如果当前木棍长度与前一个相同，且前一个未使用，则跳过// 因为相同的长度尝试顺序会产生重复的组合if(i&&!used[i-1]&&stick[i]==stick[i-1])continue;// 情况1：加上当前木棍恰好等于目标长度if(sum+stick[i]==goal){used[i]=1;// 当前大木棍拼完，开始拼下一根if(dfs(0,0,count+1))returntrue;used[i]=0;// 剪枝2：最后一根木棍必须被使用，如果它导致失败，则无解returnfalse;}// 情况2：加上当前木棍小于目标长度，继续尝试elseif(sum+stick[i]<goal){used[i]=1;if(dfs(sum+stick[i],i+1,count))returntrue;used[i]=0;// 剪枝3：如果当前大木棍的第一根木棍导致失败，则无解// 因为这是剩余可用的最大木棍if(sum==0)returnfalse;}}returnfalse;}intmain(intargc,char*argv[]){while(cin>>n,n){intlength=0;for(inti=0;i<n;i++){cin>>stick[i];length+=stick[i];}// 降序排序，优先尝试大木棍，便于剪枝sort(stick,stick+n,greater<int>());// 枚举可能的原始长度for(goal=stick[0];goal<=length;goal++){// 原始长度必须是总长度的约数if(length%goal!=0)continue;total=length/goal;memset(used,0,sizeof(used));if(dfs(0,0,0)){cout<<goal<<'\n';break;}}}return0;}

总结

本题的核心在于：

1. 枚举约数：原始长度必须是总长度的约数
2. 降序排序：优先处理大木棍，便于剪枝
3. 多种剪枝策略：重复元素剪枝、第一根失败剪枝、最后一根失败剪枝

关键点回顾

剪枝的重要性

本题的搜索空间理论上是指数级的，但通过上述剪枝策略，实际运行效率极高。这体现了在搜索问题中，合理的剪枝往往比复杂的算法更有效。这种“枚举 + 剪枝”的解题模式，在处理组合划分问题时具有通用性。