UVA 1388 Graveyard：圓周上雕塑均勻分布的最小移動距離

題目大意

有一條周長為 10000 的圓，上面等距分布著 n 個雕塑。現再加入 m 個雕塑（位置任意），希望 n+m 個雕塑最終仍能均勻分布。允許移動現有雕塑，求移動距離總和的最小值。

數學建模與推導

假設某一原有雕塑不動，作為座標原點。其他 n-1 個原有雕塑按逆時針方向，其到原點的弧長距離按比例縮放後標記為 pos。目標是將它們移動到最近的目標均勻位置。

令總周長 L = 10000。原有間距 d0 = L / n，目標間距 d1 = L / (n+m)。第 i 個原有雕塑（i=1..n-1）的原始位置 t = i * d0。其目標位置為 k * d1（k 為整數）。移動距離為 min(|t - k*d1|, |t - (k+1)*d1|)，其中 k = floor(t / d1)。

兩種實現方式

方法一：四捨五入近似（劉汝佳《算法訓練指南》例題）

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() {
    int n, m;
    while (cin >> n >> m) {
        double ans = 0.0;
        for (int i = 1; i < n; i++) {
            double pos = (double)i / n * (n + m); // 縮放後的位置
            ans += fabs(pos - floor(pos + 0.5)) / (n + m);
        }
        cout << fixed << setprecision(4) << ans * 10000 << endl;
    }
}

原理：floor(pos + 0.5) 相當於四捨五入到最近整數，對應最近的目標位置索引。雖然嚴格證明需比較前後兩個位置，但因相鄰目標位置間距為 1（縮放後），誤差 < 0.5 時四捨五入等價於取最近值。

方法二：嚴格比較前後兩個位置（更穩健）

#include <stdio.h>
#include <math.h>
const double len = 10000;
int n, m; double d0, d1;

int main() {
    while (~scanf("%d%d", &n, &m)) {
        if (m % n == 0) { printf("0.0\n"); continue; }
        d0 = len / (n * 1.0);
        d1 = len / ((n + m) * 1.0);
        double ans = 0.0;
        for (int i = 1; i < n; i++) {
            double t = i * d0;
            int d = floor(t / d1);
            double t1 = fabs(t - d * d1);
            double t2 = fabs(t - (d + 1.0) * d1);
            ans += (t1 < t2) ? t1 : t2;
        }
        printf("%.4lf\n", ans);
    }
    return 0;
}

關鍵點總結

• 座標縮放：將周長正規化，轉化為單位圓上的位置索引運算，最後再乘回 10000。
• 對稱性利用：固定一個雕塑不動，利用圓的旋轉對稱性消除一個自由度。
• 精度處理：使用 double 並輸出小數點後 4 位，滿足題目精度要求。
• 特殊情況：若 m % n == 0，目標位置與原位置完全重合，答案為 0。