UVA 434 Matty's Blocks - 積木堆疊的最小與最大數量

問題描述

給定一個 n × n 的底面，以及從正視圖和右視圖看到的每列積木高度。要求計算搭建該形狀所需的最少積木塊數，以及最多積木塊數與最少積木塊數的差值。

核心思路

最少積木數

要使積木總數最少，應盡量讓正視圖和右視圖的高度「共用」同一根柱子。具體做法：統計正視圖中每種高度出現的次數 cnt1[h]，右視圖中每種高度出現的次數 cnt2[h]。對於每個高度 h，至少需要 max(cnt1[h], cnt2[h]) 根高度為 h 的柱子。最少總數 = Σ h * max(cnt1[h], cnt2[h])。

最多積木數

要使積木總數最多，應在每一層都盡量鋪滿。模擬逐層剝除：每一層中，正視圖和右視圖都有積木的位置可以放一塊。具體算法：同時從正視圖和右視圖的最高層開始，每次將所有非零高度減 1，該層可放的積木數 = (正視圖非零列數) × (右視圖非零列數)。累加所有層即得最大總數。

複雜度

n ≤ 10，高度 ≤ 10。最少積木計算 O(n + H)，最多積木模擬 O(H * n)，極快。

參考代碼 (C++)

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 10;
int a[MAXN+1], b[MAXN+1];
int cnt1[MAXN+1], cnt2[MAXN+1];
int n;

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

int getMax() {
    int tmpA[MAXN+1], tmpB[MAXN+1];
    memcpy(tmpA, a, sizeof(a));
    memcpy(tmpB, b, sizeof(b));
    int sum = 0;
    while (true) {
        int c1 = 0, c2 = 0;
        for (int i = 1; i <= n; ++i) if (tmpA[i]) { ++c1; --tmpA[i]; }
        for (int i = 1; i <= n; ++i) if (tmpB[i]) { ++c2; --tmpB[i]; }
        if (!c1 && !c2) break;
        sum += c1 * c2;
    }
    return sum;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        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 mn = getMin();
        int mx = getMax();
        printf("Matty needs at least %d blocks, and can add at most %d extra blocks.\n", mn, mx - mn);
    }
    return 0;
}