HDU 2088 Box of Bricks：移動最少磚塊使各堆等高

題目大意

有 n 堆磚塊，高度各異。每次移動一塊磚從一堆到另一堆。求使所有堆高度相等的最少移動次數。

數學解法

目標高度 = 平均高度 avg = sum / n (題目保證整除)。
只需統計「高於平均」的堆超出部分總和，即為最少移動數。因為每移動一塊，必從高堆移到低堆，高堆總超出量 = 低堆總缺口量。

完整程式碼 (C++)

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, tc = 0;
    while (cin >> n && n) {
        if (tc++) cout << '\n';
        vector h(n);
        long long sum = 0;
        for (int i = 0; i < n; ++i) { cin >> h[i]; sum += h[i]; }
        int avg = sum / n;
        int moves = 0;
        for (int x : h) if (x > avg) moves += x - avg;
        cout << moves << '\n';
    }
    return 0;
}

複雜度

• 時間：O(n) 每測資。
• 空間：O(n) 或 O(1) (邊讀邊算)。

關鍵點

• 輸入以 0 結束，測資間需空行 (首測資前無空行)。
• 平均高度必為整數 (題目隱含條件)。
• 移動次數 = Σ max(0, hᵢ - avg)。