UVA434 - Matty's Blocks

UVA434 - Matty's Blocks

題目鏈接

題意：給出n，代表所要用積木搭建的整體的底面積的邊長，然後分別給出正視圖和右視圖，要你求出搭建都要形狀的最小木塊數量和最小木塊數量和最大木塊數量的差值。

思路：其實題目就是要你求出最小木塊數和最大木塊數，我們可以分開求解。
首先對於最小木塊數，要想用最少的立方體搭建，那就意味著正視圖中的每一豎立方體的高度最好都要被右視圖中的高度所利用到。所以我們以正視圖為基准，正視圖需要的立方體總數加上側視圖存在無法利用正視圖的數量，就是最少需要的立方體數。其次對於最大木塊數，我們也以正視圖為基准，再對照右視圖，一層一層計算木塊數，盡量每一層都能鋪滿，然後累加上去就是最大的木塊數了。

#include 
#include 
#include 
#include 

using namespace std;

const int MAXN = 10;

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

int getMin() {
    memset(num1, 0, sizeof(num1));
    memset(num2, 0, sizeof(num2));
    for (int i = 1; i <= n; i++) {  
        num1[a[i]]++;  
        num2[b[i]]++;  
    }  
    int sum = 0;  
    for (int i = 1; i <= MAXN; i++)  
        sum += max(num1[i], num2[i]) * i;  
    return sum;
}

int getMax() {
    int cnt1, cnt2, sum = 0;
    while (1) {
        cnt1 = 0;
        for (int i = 1; i <= MAXN; i++)
            if (a[i]) {
                cnt1++;
                a[i]--;
            }
        cnt2 = 0;
        for (int i = 1; i <= MAXN; i++) 
            if (b[i]) {
                cnt2++; 
                b[i]--; 
            }
        if (!cnt1 && !cnt2) break;
        sum += cnt1 * cnt2; 
    }
    return sum;
}

int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d", &n);         
        for (int i = 1; i <= n; i++)  
            scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++)  
            scanf("%d", &b[i]);
        int Min = getMin();
        int Max = getMax();
        printf("Matty needs at least %d blocks, and can add at most %d extra blocks.\n", Min, Max - Min);
    }
    return 0;
}