首页 > 代码库 > UVA1445-Cubist Artwork

UVA1445-Cubist Artwork

题目链接


题意:用一些等大的立方体搭积木,每个立方体或者直接放在地面的网格上,或者放在另一个立方体的上面,给出正视图和侧视图,求出最少用多少个立方体搭建。

思路:要想用最少的立方体搭建,那就意味着正面所看到的每一竖立方体的高度wh最好都要被侧面看到的高度dh所利用到。所以我们以正面为基准,正面需要的立方体总数加上侧面存在dh无法利用正面wh的数量,就是最少需要的立方体数。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 100;

int a[MAXN], b[MAXN], num1[MAXN], num2[MAXN];

int main() {
    int w, d;
    while (scanf("%d%d", &w, &d) && w && d) {
        memset(num1, 0, sizeof(num1));
        memset(num2, 0, sizeof(num2));
        for (int i = 1; i <= w; i++) {
            scanf("%d", &a[i]); 
            num1[a[i]]++;
        }
        for (int i = 1; i <= d; i++) {
            scanf("%d", &b[i]); 
            num2[b[i]]++;
        }
        int sum = 0;
        for (int i = 1; i <= MAXN; i++)
            sum += max(num1[i], num2[i]) * i;
        printf("%d\n", sum); 
    }
    return 0;
}