zzuliOJ 2263 neighbor

Description:

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

Input:

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

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

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

Output:

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

Sample Input:

2 2
1 1
1 1

Sample Output:

2 4

题目连接

最小值是先把所有的数加起来然后每一行找一列高度相同的减去，因为高度相同可以共用，这里注意一列只能减一次，需要判断。
而最大值则是最每一行每一列都去此行列限制高度的最小值之和。

AC代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3+5;
const double eps = 1e-5;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;
 
int n, m;
int front_view[maxn];
int left_view[maxn];
int sum;
int min_ans, max_ans;
set<int> mh;
 
int main() {
    sum = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &front_view[i]);
        sum += front_view[i];
    }
    for (int i = 0; i < m; ++i) {
        scanf("%d", &left_view[i]);
        sum += left_view[i];
    }
    min_ans = sum, max_ans = 0;
    for (int i = 0; i < n; ++i) {
        bool flag = 0;
        for (int j = 0; j < m; ++j) {
            max_ans += front_view[i] < left_view[j] ? front_view[i] : left_view[j];
            if (front_view[i] == left_view[j] && !flag && !mh.count(j)) {
                min_ans -= left_view[j];
                mh.insert(j);
                flag = 1;
            }
        }
    }
    printf("%d %d\n", min_ans, max_ans);
    return 0;
}