题目描述有一堆立方体盒子它们上表面开口因此较小的盒子会落入较大的盒子中而较大的盒子会停留在堆叠的顶部。盒子具有特殊性质它们对更小的盒子是可渗透的因此一个盒子可以穿过较大盒子的内部直到遇到更小的盒子或地面。但有一个限制如果一个盒子不能完全放入潜在容器的内部高度那么它就会停留在可能的上层位置。给定一系列盒子需要计算最终堆叠的总高度。所有盒子的尺寸互不相同。输入格式输入包含多个测试用例相邻测试用例之间用一个空行分隔。每个测试用例的第一行包含盒子数量NCNCNC1≤NC≤1001 \le NC \le 1001≤NC≤100随后NCNCNC行每行包含一个盒子的边长整数。输出格式对于每个测试用例输出一行一个整数表示总堆叠高度。样例输入8 10 4 6 3 11 7 8 5样例输出24题目分析本题要求模拟盒子逐个落下并堆叠的过程最终计算整个堆叠的总高度。盒子的堆叠规则具有递归性质当一个新盒子落下时它首先尝试进入当前堆叠中最顶层的盒子内部若该盒子内部已有更小的盒子则新盒子继续尝试进入那些更小的盒子内部直到找到一个合适的容器或者无法继续深入。关键限制是盒子必须完全放入容器的内部高度。这意味着容器内部剩余的空间高度必须大于等于新盒子的高度。由于所有盒子尺寸互不相同每个盒子最多只能容纳一个比它小的盒子直接容纳但通过递归嵌套一个盒子可以间接容纳多个更小的盒子。最终的总高度由堆叠中所有“顶层”盒子的高度之和决定这些顶层盒子是直接放置在地面上的盒子即没有被其他盒子容纳的盒子。每个顶层盒子的高度等于其自身高度加上其内部嵌套结构的总高度但题目要求计算的是整个堆叠的总高度即所有顶层盒子高度之和。解题思路使用数组lengthOfBox存储每个盒子的边长pile存储每个盒子内部容纳的盒子列表cntOfPile记录每个盒子内部直接容纳的盒子数量sizeOfPile记录每个盒子内部已占用的高度。对于每个新盒子从地面层编号为000的虚拟容器开始尝试放置。函数fit(pileId, boxId)尝试将盒子boxId放入容器pileId中。首先遍历容器pileId中已直接容纳的所有盒子对于每个已容纳的盒子若新盒子比它小则递归尝试将新盒子放入该盒子内部。若递归成功则返回真。若无法放入任何已容纳的盒子内部则检查当前容器pileId是否有足够的剩余高度容纳新盒子若sizeOfPile[pileId] lengthOfBox[boxId] lengthOfBox[pileId]则将新盒子直接放入该容器更新cntOfPile和sizeOfPile返回真。若均不满足返回假。对于每个新盒子首先尝试从地面层开始放置。若fit(0, i)返回假说明该盒子无法放入任何现有容器则将其作为新的顶层盒子直接放在地面上即加入pile[0]并更新cntOfPile[0]。处理完所有盒子后遍历pile[0]中所有顶层盒子将它们的边长累加即为总堆叠高度。时间复杂度为O(n2)O(n^2)O(n2)空间复杂度为O(n2)O(n^2)O(n2)对于n≤100n \le 100n≤100完全可行。代码实现// A Pile of Boxes// UVa ID: 946// Verdict: Accepted// Submission Date: 2021-12-27// UVa Run Time: 0.000s//// 版权所有C2021邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intlengthOfBox[128],pile[128][128],cntOfPile[128],sizeOfPile[128];boolfit(intpileId,intboxId){for(inti0;icntOfPile[pileId];i){if(lengthOfBox[boxId]lengthOfBox[pile[pileId][i]])continue;if(fit(pile[pileId][i],boxId))returntrue;}if(pileIdsizeOfPile[pileId]lengthOfBox[boxId]lengthOfBox[pileId]){pile[pileId][cntOfPile[pileId]]boxId;sizeOfPile[pileId]lengthOfBox[boxId];returntrue;}returnfalse;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intn;while(cinn){memset(cntOfPile,0,sizeofcntOfPile);memset(sizeOfPile,0,sizeofsizeOfPile);for(inti1;in;i){cinlengthOfBox[i];if(!fit(0,i))pile[0][cntOfPile[0]]i;}intheight0;for(inti0;icntOfPile[0];i)heightlengthOfBox[pile[0][i]];coutheight\n;}return0;}总结本题的关键在于理解盒子堆叠的递归嵌套规则并正确实现fit函数。地面层使用编号000的虚拟容器表示其高度限制为无穷大因此只需检查是否有足够空间容纳新盒子即可。注意fit函数中递归尝试放入已容纳盒子的内部时必须确保新盒子比当前已容纳的盒子小否则跳过。最终总高度为所有直接放在地面上的顶层盒子的边长之和。时间复杂度为O(n2)O(n^2)O(n2)空间复杂度为O(n2)O(n^2)O(n2)能够高效处理题目规模的数据。