首页 > 代码库 > 地形图
地形图
【题目描述】
地形图可通过一个高度矩阵表示，矩阵中每一个位置都有一个数hij(0 <= hij <= 105)表示这个坐标的海拔，称为海拔图。
现已知主视图、左视图，询问可能的体积的最大值和最小值。
【输入描述】
第一行输入两个数n、m，分别表示海拔图的长和宽；
第二行输入n个数，表示主视图上每一个位置的高度；
第三行输入m个数，表示左视图上每一个位置的高度。
【输出描述】
输出两个数，分别表示可能的体积的最大值和最小值。
【输入样例】
2 2
1 1
1 1
【输出样例】
2 4
【数据范围及提示】
样例中，最大最小值对应的海拔图分别为：
1 1 1 0
1 1 0 1
对于10%的数据，n = m = 1；
对于10%的数据，n = m = 2；
对于20%的数据，1 <= n,m <= 3，0 <= hij <= 3；
对于100%的数据，1 <= n,m <= 1000，0 <= hij <= 1000。
源代码：#include<cstdio>#include<algorithm>using namespace std;int n,m,Max,Min,Front[1001],Left[1001];bool f1[1001],f2[1001];int main() { scanf("%d%d",&n,&m); for (int a=1;a<=n;a++) scanf("%d",&Front[a]); for (int a=1;a<=m;a++) scanf("%d",&Left[a]); for (int a=1;a<=n;a++) for (int b=1;b<=m;b++) { Max+=min(Front[a],Left[b]); if (Front[a]==Left[b]&&!f1[a]&&!f2[b]) //累加重合部分。 { f1[a]=f2[b]=true; Min+=Front[a]; } } for (int a=1;a<=n;a++) //如果不加，不符题意，故必须加上。 if (!f1[a]) //找到过即为重合部分。 Min+=Front[a]; for (int a=1;a<=m;a++) if (!f2[a]) Min+=Left[a]; printf("%d %d",Max,Min); return 0;}/* 这道题需要动点脑子。 寻找最大体积的思想应该是贪得无厌，只要符合题意就加上，即为：Max+=min(Front[i],Left[j])； 寻找最小体积的思想应该是迫不得已，先把重合的部分加上，再把符合题意的临界部分加上。*/
地形图
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。