UVa 434 Matty‘s Blocks

题目描述题目要求根据建筑物的前视图和右视图确定重建该建筑物所需的最少积木数量NNN以及在不改变前后视图的情况下最多可以额外添加的积木数量MMM。建筑物由K×KK \times KK×K个格子组成K8K 8K8为最大尺寸每个格子上堆叠000到888个积木。前视图给出了每列的最大高度右视图给出了每行的最大高度。需要找到最少积木数NNN使得存在一种积木放置方式其前视图和右视图与给定视图一致。最多可添加积木数MMM在保持视图不变的前提下从最少积木数出发最多还能添加多少积木。输入格式第一行一个整数TTT表示测试用例的数量。每个测试用例第一行一个整数KKK表示表格的宽度即视图的长度。第二行KKK个整数表示前视图从左到右每列的最大高度。第三行KKK个整数表示右视图从前到后每行的最大高度顺序对应前视图的列实际右视图中第iii个数字对应第iii行的最大高度。输出格式对于每个测试用例输出一行Matty needs at least N blocks, and can add at most M extra blocks.样例输入2 4 2 0 3 1 1 1 2 3 1 1 1输出Matty needs at least 7 blocks, and can add at most 10 extra blocks. Matty needs at least 1 blocks, and can add at most 0 extra blocks.题目分析本题的核心是根据前视图和右视图确定积木放置的最小可能总数和最大可能总数。最大积木数NMN MNM在保持前视图和右视图不变的前提下每个位置(i,j)(i, j)(i,j)第iii行第jjj列可以放置的积木数量上限为maxBlocks[i][j]min⁡(frontView[j],rightView[i]) maxBlocks[i][j] \min(frontView[j], rightView[i])maxBlocks[i][j]min(frontView[j],rightView[i])这是因为该位置的高度不能超过其所在列的前视图高度也不能超过其所在行的右视图高度。将所有位置的最大值相加即得到可能的最大积木总数maxTotal∑i1K∑j1Kmin⁡(frontView[j],rightView[i]) maxTotal \sum_{i1}^{K} \sum_{j1}^{K} \min(frontView[j], rightView[i])maxTotali1∑K​j1∑K​min(frontView[j],rightView[i])最小积木数NNN为了达到最少积木数应尽可能让一个积木同时满足前视图和右视图的贡献。具体策略对于每个前视图高度hfh_fhf​尝试在右视图中找到一个相同高度的hrh_rhr​将这两个视图的贡献用一个积木塔来满足。一个hhh高度的塔同时满足前视图中该列需要至少hhh和右视图中该行需要至少hhh。因此对每个高度值匹配尽可能多的前视图列和右视图行。一旦匹配成功该高度hhh贡献hhh个积木并消除对应的前视图和右视图需求。未匹配的前视图高度和右视图高度只能由单独的积木塔来满足贡献其高度值。算法步骤复制前视图数组front\textit{front}front和右视图数组right\textit{right}right。对于front\textit{front}front中的每个高度fff在right\textit{right}right中寻找相同的值。若找到则将该高度贡献到minBlocks\textit{minBlocks}minBlocks加上fff并将该right\textit{right}right元素置为000表示已匹配同时跳出内层循环继续处理下一个front\textit{front}front元素。遍历结束后将front\textit{front}front和right\textit{right}right中剩余的非零值相加得到额外的积木数。最终minBlocks\textit{minBlocks} minBlocks匹配贡献之和 剩余前视图之和 剩余右视图之和。可添加积木数MMMMmaxTotal−minBlocks M maxTotal - minBlocksMmaxTotal−minBlocks复杂度分析每个测试用例需要O(K2)O(K^2)O(K2)计算最大积木数O(K2)O(K^2)O(K2)计算最小积木数K≤8K \le 8K≤8完全可接受。代码实现// Mattys Blocks// UVa ID: 434// Verdict: Accepted// Submission Date: 2016-07-29// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases0;cincases;for(inti1;icases;i){introw;cinrow;vectorintfront_view(row),right_view(row);for(intj0;jrow;j)cinfront_view[j];for(intj0;jrow;j)cinright_view[j];intmax_blocks0;for(intj0;jrow;j)for(intk0;krow;k)max_blocksmin(right_view[j],front_view[k]);intmin_blocks0;for(intj0;jrow;j)for(intk0;krow;k)if(front_view[j]right_view[k]){min_blocksfront_view[j];front_view[j]0;right_view[k]0;break;}for(intj0;jrow;j)min_blocksfront_view[j]right_view[j];coutMatty needs at least min_blocks;cout blocks, and can add at most ;cout(max_blocks-min_blocks) extra blocks.\n;}return0;}