PAT-B 1023 組個最小數：貪心策略構造最小整數完整解析

題目大意

給定 0-9 各數字個數 (共 ≤ 50 位，至少一個非 0)，用盡所有數字拼成最小整數 (首位不可為 0)。

貪心策略

1. 找最小非 0 數字 (1-9) 作為首位，個數 -1。
2. 從 0 到 9 依序輸出剩餘所有數字。

證明：最高位權重最大，選最小非 0 數字使整體最小；後續位權重遞減，按升序排列使後綴最小。

範例追蹤

輸入：2 2 0 0 0 3 0 0 1 0 (兩個 0、兩個 1、三個 5、一個 8)
步驟 1：最小非 0 為 1 → 首位 1，剩餘 1:1
步驟 2：升序輸出 → 0 0 1 5 5 5 8
結果：10015558 ✅

標準 C 代碼

#include <cstdio>

int main() {
    int cnt[10];
    for (int i = 0; i < 10; i++) scanf("%d", &cnt[i]);

    // 找首位
    int first = 1;
    while (first < 10 && cnt[first] == 0) first++;
    printf("%d", first);
    cnt[first]--;

    // 輸出剩餘
    for (int d = 0; d < 10; d++)
        while (cnt[d]-- > 0) printf("%d", d);

    return 0;
}

邊界情況處理

• 輸入全為 0 除一個非 0：如 1 0 0 ... 0 → 輸出 1。
• 大量 0：如 49 1 0 ... 0 → 1 + 49 個 0，共 50 位，符合限制。
• 無非 0 數字：題目保證至少一個，無需處理。

複雜度分析

• 時間：O(10 + 總位數) = O(1) (上限 50 位)。
• 空間：O(1) (固定 10 元素陣列)。

總結

PAT-B 1023 以貪心構造最小整數：首位取最小非 0，其餘升序。代碼極簡、邏輯嚴密、邊界清晰，是貪心算法入門的經典範例。