隔壁_牛客博客

问题 F: neighbor

时间限制: 1 Sec 内存限制: 256 MB
</center>

题目描述

隔壁学校地形图可以通过一个高度矩阵表示，矩阵中每一个位置都有一个数hi , j表示这个坐标的海拔，我们姑且将其称为海拔图，容易发现，我们可以通过这个矩阵轻松算出隔壁学校的主视图，左视图。
相反的，我们却不能通过主视图和左视图唯一确定海拔图，现在问题来了，已知主视图左视图，我们需要知道铲平隔壁学校的代价上限和下限(即可能的体积最大值与最小值)

输入

第一行两个数 n , m (1 <=n ,m<=1000, 0<= hi ,j <= 1000), 分别表示海拔图的长和宽。

第二行 n 个数，描述了主视图每一个位置的高度。

第三行 m 个数，描述了左视图每一个位置的高度

输出

一行两个数，分别表示代价最小值与最大值。

样例输入

2 2
1 1
1 1

样例输出

2 4

#include<stdio.h>
#define min(a, b) a < b ? a : b
int main()
{
    int n, m, a[1010], b[1010], s[1010], min_ans, max_ans, flag;
    while (~scanf("%d%d", &n, &m))
    {
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        for(int i = 0; i < m; i++)
            scanf("%d", &b[i]);
        min_ans = 0;
        max_ans = 0;
        for (int i = 0; i < n; i++)
        {
            flag = 0;
            for (int j = 0; j < m; j++)
            {
                if(a[i] == b[j] && !s[j])
                {
                    min_ans += a[i];
                    s[j] = 1;
                    flag = 1;
                    break;
                }
            }
            if(!flag)
            min_ans += a[i];
        }
        for(int i = 0; i < m; i++)
        {
            if(!s[i])
                min_ans += b[i];
        }
        max_ans = 0;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
                max_ans += min(a[i], b[j]);
        }
        printf("%d %d\n", min_ans, max_ans);
    }
    return 0;
}