UVA 11300 Spreading the Wealth：環形分金幣與中位數優化

題目大意

n 個人圍成一圈分金幣，每人初始有 A[i] 個。每次操作：每人將一半金幣給右邊鄰居（或類似傳遞規則），最終希望每人擁有相同數量（平均值 M = sum/n）。求最少移動次數（或總移動距離）。

實際為經典「環形負載均衡」問題，劉汝佳《算法競賽入門經典》例題。

數學推導

設 x_i 為第 i 人最終給左鄰居（或接收）的金幣數（正為給出，負為接收）。平衡方程：

A[1] - x_1 + x_n = M
A[2] - x_2 + x_1 = M
...
A[n] - x_n + x_{n-1} = M

遞推得：

x_1 = x_1
x_2 = x_1 - (A[1] - M)
x_3 = x_2 - (A[2] - M) = x_1 - (A[1]+A[2] - 2M)
...
x_i = x_1 - C[i]   其中 C[i] = sum_{j=1}^{i-1} (A[j] - M), C[1] = 0

總移動代價 = sum |x_i| = sum |x_1 - C[i]|。這是一維絕對值距離和最小化問題，最優 x_1 為 C[] 的中位數。

程式碼實現

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define MAX 1000010
long long A[MAX], C[MAX];
long long n, sum, tot, aver;

void input() {
    tot = 0;
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        tot += A[i];
    }
}

void build_C() {
    aver = tot / n;
    C[0] = 0;
    for (int i = 1; i < n; i++)
        C[i] = C[i-1] + A[i] - aver;
}

void solve() {
    sort(C, C + n);
    long long mid = C[n/2]; // 中位數
    sum = 0;
    for (int i = 0; i < n; i++)
        sum += llabs(C[i] - mid);
    cout << sum << endl;
}

int main() {
    while (cin >> n) {
        memset(A, 0, sizeof(A));
        memset(C, 0, sizeof(C));
        sum = 0; tot = 0;
        input();
        build_C();
        solve();
    }
    return 0;
}

關鍵點總結

1. 環轉線性：固定 x_1 為變量，其他變量用 x_1 表示，利用環狀結構的遞推關係。
2. 前綴和構造 C 數組：C[i] 代表前 i 個人與平均值的累積偏差。
3. 中位數性質：sum |x - a_i| 在 x 為中位數時取得最小值。
4. 數據類型：long long 防止溢出（n ≤ 1e6，金幣數可能大）。
5. 特殊情況：若 tot % n != 0 無解，但題目保證可整除。

複雜度

• 時間：O(n log n)（排序主導），可用 O(n) 選取算法優化至 O(n)。
• 空間：O(n)。