当前位置：首页 > news >正文

UVa 434 Matty‘s Blocks

news 2026/6/9 23:15:03

题目描述

题目要求根据建筑物的前视图和右视图，确定重建该建筑物所需的最少积木数量NNN，以及在不改变前后视图的情况下最多可以额外添加的积木数量MMM。建筑物由K×KK \times KK×K个格子组成（K=8K = 8K=8为最大尺寸），每个格子上堆叠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.

题目分析

本题的核心是根据前视图和右视图，确定积木放置的最小可能总数和最大可能总数。

最大积木数N+MN + MN+M

在保持前视图和右视图不变的前提下，每个位置(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=∑i=1K∑j=1Kmin⁡(frontView[j],rightView[i]) maxTotal = \sum_{i=1}^{K} \sum_{j=1}^{K} \min(frontView[j], rightView[i])maxTotal=i=1∑Kj=1∑Kmin(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=匹配贡献之和 + 剩余前视图之和 + 剩余右视图之和。

可添加积木数MMM

M=maxTotal−minBlocks M = maxTotal - minBlocksM=maxTotal−minBlocks

复杂度分析

每个测试用例需要O(K2)O(K^2)O(K2)计算最大积木数，O(K2)O(K^2)O(K2)计算最小积木数，K≤8K \le 8K≤8，完全可接受。

代码实现

// Matty's Blocks// UVa ID: 434// Verdict: Accepted// Submission Date: 2016-07-29// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases=0;cin>>cases;for(inti=1;i<=cases;i++){introw;cin>>row;vector<int>front_view(row),right_view(row);for(intj=0;j<row;j++)cin>>front_view[j];for(intj=0;j<row;j++)cin>>right_view[j];intmax_blocks=0;for(intj=0;j<row;j++)for(intk=0;k<row;k++)max_blocks+=min(right_view[j],front_view[k]);intmin_blocks=0;for(intj=0;j<row;j++)for(intk=0;k<row;k++)if(front_view[j]==right_view[k]){min_blocks+=front_view[j];front_view[j]=0;right_view[k]=0;break;}for(intj=0;j<row;j++)min_blocks+=front_view[j]+right_view[j];cout<<"Matty needs at least "<<min_blocks;cout<<" blocks, and can add at most ";cout<<(max_blocks-min_blocks)<<" extra blocks.\n";}return0;}