UVA 311 Packets：貪心裝箱，6×6 箱子裝 1×1 到 6×6 包裹

問題描述

有 6 種包裹，尺寸分別為 1×1、2×2、3×3、4×4、5×5、6×6，需裝入 6×6 的箱子。輸入每種包裹的數量，求最少需要多少個箱子。多組測試，全 0 結束。

貪心策略：從大到小依次放置，利用剩餘空間填充小包裹

箱子面積 36。關鍵規律：

• 6×6：佔滿一箱，直接計數。
• 5×5：每個佔 25，剩 11 格只能放 1×1，每箱最多放 11 個 1×1。
• 4×4：每個佔 16，剩 20 格可放 5 個 2×2，不足再用 1×1 填補（每少一個 2×2 需 4 個 1×1）。
• 3×3：4 個剛好佔滿一箱（36）。餘數 1/2/3 分別需配 5 個 2×2+7 個 1×1、3 個 2×2+6 個 1×1、1 個 2×2+5 個 1×1。
• 2×2：9 個佔滿一箱。餘數 r 需 36 - 4r 個 1×1 填補。
• 1×1：36 個一箱。

代碼實現（C++）

#include <cstdio>
#include <algorithm>
using namespace std;

int p[7]; // 1-based

int main() {
    while (true) {
        int sum = 0, flag = 0;
        for (int i = 1; i <= 6; ++i) {
            scanf("%d", &p[i]);
            flag += p[i];
        }
        if (!flag) break;

        sum += p[6];                    // 6x6
        // 5x5
        if (p[5]) {
            sum += p[5];
            p[1] -= p[5] * 11;
        }
        // 4x4
        if (p[4]) {
            sum += p[4];
            p[2] -= p[4] * 5;
            if (p[2] < 0) { p[1] += p[2] * 4; p[2] = 0; }
        }
        // 3x3
        if (p[3]) {
            sum += p[3] / 4;
            int r = p[3] % 4;
            if (r) {
                ++sum;
                if (r == 1) { p[2] -= 5; p[1] -= 7; }
                else if (r == 2) { p[2] -= 3; p[1] -= 6; }
                else if (r == 3) { p[2] -= 1; p[1] -= 5; }
                if (p[2] < 0) { p[1] += p[2] * 4; p[2] = 0; }
            }
        }
        // 2x2
        if (p[2] > 0) {
            sum += p[2] / 9;
            int r = p[2] % 9;
            if (r) { ++sum; p[1] -= 36 - r * 4; }
        }
        // 1x1
        if (p[1] > 0) {
            sum += p[1] / 36;
            if (p[1] % 36) ++sum;
        }
        printf("%d\n", sum);
    }
    return 0;
}

複雜度

常數時間 O(1)，極快。