ACM 經典題：Box of Bricks (搬磚最少次數使所有堆高度相等)

這是 UVa 591 / POJ 1477 等 OJ 的經典題目。Bob 有 n 堆磚塊，高度各異。想將磚塊搬移使所有堆高度相同，求最少搬移磚塊數。條件：總磚塊數可被 n 整除，n ≤ 50，高度 ≤ 100。輸入多組測資，n=0 結束。

解題觀念

• 目標高度 = 總磚塊數 / 堆數（平均值）。
• 只需計算「高於平均」的堆超出部分的總和，即為最少搬移數（因每搬一塊磚必從高堆移到低堆）。

演算法步驟

1. 讀取 n，若 0 則結束。
2. 讀取 n 個高度，累加總和。
3. 計算平均 avg = sum / n。
4. 遍歷陣列，若 h[i] > avg 則 moves += h[i] - avg。
5. 輸出格式：Set #k、The minimum number of moves is X.、空行。

C 語言實作

#include <stdio.h>

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

    while (scanf("%d", &n) == 1 && n != 0) {
        sum = moves = 0;
        for (i = 0; i < n; i++) scanf("%d", &h[i]);
        for (i = 0; i < n; i++) sum += h[i];
        average = sum / n;
        for (i = 0; i < n; i++)
            if (h[i] > average) moves += h[i] - average;

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

樣例

輸入：
6
5 2 4 1 7 5
0

輸出：
Set #1
The minimum number of moves is 5.

複雜度分析

時間 O(n)，空間 O(n)，極其高效。