题目分析

目的:在已知正视图与侧视图的基础上求出最少要用的立方体数量。

对于正视图与侧视图来说对应数字实际上就是视线正对方向的最大数字。

观察下图,了解正视图与侧视图的含义。

pFsh0YV.png

思考,如何根据两种视图确定最小的总和。

图上的数字要尽可能少,如下图中的几个位置的数字能同时满足两种视图,这样的数字在两种视图中只需要计算一次即可。我们要尽可能找这种数字。

pFsfHI0.png

首先,按照正视图的顺序进行遍历,去查看是否存在数字在侧视图中与之匹配,标记对应数字在侧视图中的位置,这样侧视图中该数字对应位置的值就不需要重复计算了,否则的话,为了满足侧视图就需要在未标记的位置增加对应数字。

以正视图 $1\ 2\ 3\ 4\ 5$, 侧视图 $3\ 3\ 3\ 4\ 5$ 为例,分析实现过程。

遍历正视图,第一个数字为 $1$​ 在对应侧视图中不存在,在该列某行必然存在一个 $1$​ 。第二个数字为 $2$ 在对应侧视图中不存在,在该列某行必然存在一个 $2$ 。第三个数字为 $3$ 在对应侧视图中第一行存在相同的数字,标记侧视图中的第一个位置。第四个数字为 $4$ 在对应侧视图中第 $4$ 行存在相同的数字,标记侧视图中的第四个位置。第五个数字为 $5$ 在对应侧视图中第 $5$ 行存在相同的数字,标记侧视图中的第五个位置。之后遍历侧视图,未标记的位置说明对应位置的数字还得出现至少一次,将它们累加即可。

pFshGQg.png

代码实现

#include <bits/stdc++.h>
using namespace std;
int a[15][15];
int h[4][15];
int w,d;
bool vis[15];
int main()
{
    while(cin>>w>>d&&w&&d){
        //多测注意清空
        int sum=0;
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=w;i++){//输入正视图信息
            cin>>h[1][i];
        }
        for(int i=1;i<=d;i++){//输入侧视图信息
            cin>>h[2][i];
        }
        //遍历正视图
        for(int i=1;i<=w;i++){
            sum+=h[1][i];//不管是否在侧视图中找到对应数字,这个数至少出现一次
            for(int j=1;j<=d;j++){//遍历侧视图
                if(h[1][i]==h[2][j]){//寻找匹配位置
                    if(vis[j]) continue;//跳过被标记的位置,避免重复
                    vis[j]=1;//标记侧视图中的位置
                    break;
                }
            }
        }
        //遍历侧视图
        for(int i=1;i<=d;i++){
            if(!vis[i]){//累加未标记的侧视图数字
                sum+=h[2][i];
            }
        }
        cout<<sum<<endl;        
    }
    return 0;
}
最后修改:2024 年 03 月 09 日
如果觉得我的文章对你有用,请随意赞赏