C語言解題：ACM Box of Bricks 問題（最少移動磚塊數使所有堆疊等高）

ACM 經典題目：Box of Bricks

Bob 用磚塊堆出不同高度的堆疊，Alice 建議將所有堆疊調整為相同高度。目標是找出最少需要移動多少塊磚塊。此為 ACM 競程經典入門題（UVa 591）。

問題描述

• 輸入多組測資，每組第一行為堆疊數 n (1 ≤ n ≤ 50)，第二行為 n 個堆疊高度 h_i (1 ≤ h_i ≤ 100)。
• 總磚塊數可被 n 整除，故必存在解。
• n = 0 結束輸入。
• 輸出每組測資的集合編號與最少移動磚塊數 k。

解題邏輯

1. 計算所有堆疊高度總和 sum，目標高度 avg = sum / n。
2. 只需計算「高於平均高度」的堆疊超出部分總和，即為最少移動數。因為每移動一塊磚從高堆到低堆，同時減少高堆 1 並增加低堆 1，總移動數等於超出總量（或不足總量，兩者相等）。
3. 遍歷陣列，若 h[i] > avg 則 moves += h[i] - avg。

完整程式碼

#include <stdio.h>

int main()
{
    int n, i, sum, average, moves, case_num = 1;
    int heights[100];

    while(scanf("%d", &n), n != 0)
    {
        sum = moves = 0;
        for(i = 0; i < n; i++) scanf("%d", &heights[i]);

        for(i = 0; i < n; i++) sum += heights[i];
        average = sum / n;

        for(i = 0; i < n; i++)
            if(heights[i] > average) moves += heights[i] - average;

        printf("Set #%d\n", case_num);
        printf("The minimum number of moves is %d.\n\n", moves);
        case_num++;
    }
    return 0;
}

執行結果示意

範例驗證

輸入：6\n5 2 4 1 7 5\n0
總和 = 24，平均 = 4。
超出部分：5→+1, 7→+3, 5→+1，總計 5。
輸出：Set #1\nThe minimum number of moves is 5. ✓

複雜度分析

• 時間複雜度：O(n) 每測資，極快。
• 空間複雜度：O(n) 存儲高度陣列。