UVA 591 Box of Bricks - 平均值移動最小次數

題目大意

有 n 堆磚塊，每堆高度為 a[i]。每次操作可將一塊磚從一堆移到另一堆。求使所有堆高度相等（即均為平均值）所需的最少移動次數。數據保證總高度能被 n 整除。

核心洞察

目標高度 = 平均值 avg = sum / n。只需計算高於平均值的堆總共需要移出多少塊磚（或低於平均值的堆總共需要移入多少），兩者相等。因為每次移動同時減少一堆超額並增加一堆不足，所以最少次數 = Σ max(0, a[i] - avg)，等價於 (Σ |a[i] - avg|) / 2。

C 代碼實現

#include 
#include 

int main() {
    int n, a[55], caseNo = 1;
    while (scanf("%d", &n) == 1 && n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        int avg = sum / n;
        int moves = 0;
        for (int i = 0; i < n; i++)
            if (a[i] > avg) moves += a[i] - avg; // 只統計超額部分
        printf("Set #%d\n", caseNo++);
        printf("The minimum number of moves is %d.\n\n", moves);
    }
    return 0;
}

關鍵點

• 輸入以 n=0 結束，多組測試用例。
• 輸出格式需完全匹配：Set #k 換行，結果行換行，再空一行。
• 數據範圍小 (n ≤ 50)，直接模擬即可。

複雜度

• 時間：O(n) 每用例。
• 空間：O(n)。