题面
隔壁学校地形图可以通过一个高度矩阵表示,矩阵中每一个位置都有一个数表示这个坐标的海拔,我们姑且将其称为海拔图,容易发现,我们可以通过这个矩阵轻松算出隔壁学校的主视图,左视图。相反的,我们却不能通过主视图和左视图唯一确定海拔图,现在问题来了,已知主视图左视图,我们需要知道铲平隔壁学校的代价上限和下限(即可能的体积最大值与最小值)
分析
给出的正视图和侧视图其实就是那一行(列)的最大值了,因此,为避免冲突,求最大值的时候就在两个最大值中去min
而求最小值,要使出现的数字尽量少,则其他全部填0,只满足最大的点出现就可以了。
代码
#include<bits/stdc++.h> using namespace std; #define N 1010 #define ll long long #define RT register ll n,m,minx,maxx; ll a[N],b[N],flag[N]; template<class T> inline void read(T &x) { x=0;ll f=1;static char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x*=f; } int main() { read(n);read(m); for(RT ll i=1;i<=n;++i)read(a[i]); for(RT ll i=1;i<=m;++i)read(b[i]); for(RT ll i=1;i<=n;++i) for(RT ll j=1;j<=m;++j) maxx+=min(a[i],b[j]); for(RT ll i=1;i<=n;++i) { minx+=a[i]; for(RT ll j=1;j<=m;++j) { if(flag[j])continue; if(b[j]==a[i]){flag[j]=1;break;} } } for(RT ll i=1;i<=m;++i) if(!flag[i]) minx+=b[i]; printf("%lld %lld",minx,maxx); return 0; }