题目描述乔治将一些等长的木棍随机切割直到所有木棍部分的长度都不超过505050单位。现在他忘记了原始木棍的数量和长度想将这些木棍部分重新拼成原始等长木棍。请编写程序计算出原始木棍可能的最小长度。所有长度都是大于000的整数。输入格式输入文件包含多个数据块每个数据块两行第一行切割后的木棍部分数量nnn第二行nnn个木棍部分的长度用空格分隔最后一行以0表示输入结束输出格式对于每个数据块输出一行包含原始木棍的最小可能长度。样例输入9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 0样例输出6 5样例解释第一组999根木棍部分总长度52152152124521521521 2452152152124原始木棍长度为666时可以拼成444根(51,51,51,222)(51, 51, 51, 222)(51,51,51,222)第二组444根木棍部分总长度1234101234 10123410原始木棍长度为555时可以拼成222根(14,23)(14, 23)(14,23)题目分析问题的本质这是一个经典的木棍拼接问题属于“划分问题”的变种。给定若干小木棍切割后的部分要求将它们拼成若干根等长的大木棍求大木棍可能的最小长度。等价表述将nnn个数划分成若干个和相等的子集求这个和的最小可能值。数学约束设木棍部分的总长度为S∑stick[i]S \sum \text{stick}[i]S∑stick[i]原始木棍长度为LLL原始木棍数量为kS/Lk S / LkS/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甚至更大。直接枚举所有划分方案子集划分是指数级的不可行。必须使用搜索 剪枝。解题思路步骤一排序与预处理为了优化搜索将木棍部分按从大到小排序。原因大的木棍更难匹配先处理大木棍可以尽早发现不可行的情况便于剪枝如果当前剩余空间连最小的木棍都放不下可以直接回溯步骤二枚举可能的原始长度从Lstick[0]L \text{stick}[0]Lstick[0]最长部分开始依次检查每个SSS的约数。只要找到第一个可行的LLL它就是最小的可能长度因为从小到大枚举。步骤三深度优先搜索对于给定的候选长度goal需要判断能否将所有的木棍部分拼成若干根长度为goal的大木棍。搜索状态sum当前正在拼接的大木棍已经累加的长度idx当前考虑的木棍部分的起始索引count已经成功拼好的大木棍数量目标count total其中total S / goal。步骤四剪枝策略这是本题的关键。有效的剪枝可以大幅减少搜索空间整除剪枝goal必须能整除总长度S否则跳过重复元素剪枝如果当前木棍长度与前一个相同且前一个未被使用则跳过当前。因为相同的长度尝试顺序会重复产生相同的组合。if(i!used[i-1]stick[i]stick[i-1])continue;组合完成剪枝如果sum stick[i] goal说明当前大木棍恰好拼满。此时标记使用该木棍递归拼下一根大木棍dfs(0, 0, count 1)如果递归失败返回false因为当前大木棍的最后一根木棍必须被使用如果它导致后续失败则当前方案不可行起始失败剪枝如果sum 0即正在拼一根新的大木棍且当前选择的木棍导致失败则直接返回false。因为这是该大木棍的第一根木棍如果它不行任何其他木棍作为第一根也不会成功由于降序排序当前是剩余可用的最大木棍。空间不足剪枝如果sum stick[i] goal尝试继续拼接。但要注意如果当前是空木棍sum 0且选择了当前木棍后失败则直接返回false。步骤五搜索框架booldfs(intsum,intidx,intcount){if(counttotal)returntrue;// 所有大木棍都拼好了for(intiidx;in;i){if(used[i])continue;// 剪枝2跳过重复的未使用元素if(i0!used[i-1]stick[i]stick[i-1])continue;if(sumstick[i]goal){used[i]1;if(dfs(0,0,count1))returntrue;used[i]0;returnfalse;// 剪枝3最后一根木棍失败}elseif(sumstick[i]goal){used[i]1;if(dfs(sumstick[i],i1,count))returntrue;used[i]0;if(sum0)returnfalse;// 剪枝4第一根木棍失败}}returnfalse;}算法复杂度分析时间复杂度最坏情况下搜索空间是指数级的但通过多种剪枝策略实际运行效率很高n64n 64n64时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根则Sk×LS k \times LSk×L因此LLL是SSS的约数。□\square□引理 2降序排序 优先尝试大木棍不会遗漏可行解。证明如果存在一个可行解将其中每根大木棍内的木棍部分按任意顺序排列都可以通过重排得到降序搜索过程中访问到的某种顺序。因此降序搜索是完备的。□\square□引理 3剪枝策略是安全的不会剪掉可行解。证明重复元素剪枝由于排序后相同长度的木棍等价跳过重复不会丢失解最后一根木棍失败剪枝如果当前大木棍的最后一根木棍恰好填满导致后续失败则任何其他组合填满当前大木棍也会失败因为最后一根木棍是唯一的第一根木棍失败剪枝如果当前大木棍的第一根木棍导致失败则任何其他木棍作为第一根也一定会失败因为当前是剩余木棍中最长的更长的已经试过不行更短的只会留下更难以匹配的剩余空间□\square□参考代码// Sticks// UVa ID: 307// Verdict: Accepted// Submission Date: 2017-01-06// UVa Run Time: 0.100s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intstick[105];// 木棍部分的长度intused[105];// 标记是否已使用intn;// 木棍部分的数量intgoal;// 当前尝试的原始木棍长度inttotal;// 原始木棍的数量// 深度优先搜索// sum: 当前正在拼接的大木棍已累加的长度// idx: 当前考虑的木棍部分的起始索引// count: 已经成功拼好的大木棍数量booldfs(intsum,intidx,intcount){// 所有大木棍都拼好了if(counttotal)returntrue;for(intiidx;in;i){// 如果当前木棍已使用跳过if(used[i])continue;// 剪枝1如果当前木棍长度与前一个相同且前一个未使用则跳过// 因为相同的长度尝试顺序会产生重复的组合if(i!used[i-1]stick[i]stick[i-1])continue;// 情况1加上当前木棍恰好等于目标长度if(sumstick[i]goal){used[i]1;// 当前大木棍拼完开始拼下一根if(dfs(0,0,count1))returntrue;used[i]0;// 剪枝2最后一根木棍必须被使用如果它导致失败则无解returnfalse;}// 情况2加上当前木棍小于目标长度继续尝试elseif(sumstick[i]goal){used[i]1;if(dfs(sumstick[i],i1,count))returntrue;used[i]0;// 剪枝3如果当前大木棍的第一根木棍导致失败则无解// 因为这是剩余可用的最大木棍if(sum0)returnfalse;}}returnfalse;}intmain(intargc,char*argv[]){while(cinn,n){intlength0;for(inti0;in;i){cinstick[i];lengthstick[i];}// 降序排序优先尝试大木棍便于剪枝sort(stick,stickn,greaterint());// 枚举可能的原始长度for(goalstick[0];goallength;goal){// 原始长度必须是总长度的约数if(length%goal!0)continue;totallength/goal;memset(used,0,sizeof(used));if(dfs(0,0,0)){coutgoal\n;break;}}}return0;}总结本题的核心在于枚举约数原始长度必须是总长度的约数降序排序优先处理大木棍便于剪枝多种剪枝策略重复元素剪枝、第一根失败剪枝、最后一根失败剪枝关键点回顾知识点说明约数枚举LLL必须是SSS的约数且≥max⁡(stick)\geq \max(\text{stick})≥max(stick)降序排序大木棍优先便于剪枝重复元素剪枝跳过相同长度的未使用木棍第一根失败剪枝当前大木棍的第一根木棍失败则回溯最后一根失败剪枝恰好填满大木棍的最后一根木棍失败则回溯剪枝的重要性本题的搜索空间理论上是指数级的但通过上述剪枝策略实际运行效率极高。这体现了在搜索问题中合理的剪枝往往比复杂的算法更有效。这种“枚举 剪枝”的解题模式在处理组合划分问题时具有通用性。