C/C++ 每日小練（七）：墓地雕塑問題完整解析

題目背景

在一個周長為 10000 的圓周上，等距分布著 n 座原有雕塑。現需加入 m 座新雕塑（位置可任意選擇），使所有 n+m 座雕塑在圓周上均勻分布。為達此目標，必須移動部分原有雕塑。求：原有 n 座雕塑移動總距離的最小值，精確到 0.0001。

輸入輸出格式

• 輸入：多組測資，每行兩個整數 n m (2≤n≤1000, 1≤m≤1000)，EOF 結束。
• 輸出：每組一行，最小總移動距離 (放大 10000 倍後的實際距離)，保留 4 位小數。

核心數學模型

1. 座標正規化

將圓周長標準化為 1。原有 n 座雕塑位置為：

0, 1/n, 2/n, ..., (n-1)/n

目標均勻分布 n+m 座位置為：

0, 1/(n+m), 2/(n+m), ..., (n+m-1)/(n+m)

2. 固定一個參考點消除圓環對稱性

假設第 0 座雕塑 (位置 0) 不動，作為原點。其餘 n-1 座原有雕塑需移動至最接近的目標位置。第 i 座原有雕塑 (1≤i<n) 的原始位置 i/n，對應的目標位置索引為 round(i/n * (n+m))，即四捨五入後的整數。

3. 距離計算公式

第 i 座雕塑的移動距離 (單位圓周長) 為：

| i/n - round(i/n * (n+m)) / (n+m) |

等價於：

| pos - floor(pos + 0.5) | / (n+m)，其中 pos = i * (n+m) / n。

4. 總距離放大

最終答案乘以圓周長 10000：

ans = 10000 * Σ_{i=1}^{n-1} |pos_i - round(pos_i)| / (n+m)

演算法流程

1. 讀入 n, m。
2. 初始化 ans = 0。
3. 對 i = 1 .. n-1：
   • 計算 pos = (double)i / n * (n + m)。
   • 最近目標整數索引 nearest = floor(pos + 0.5)。
   • 累加 ans += fabs(pos - nearest) / (n + m)。
4. 輸出 ans * 10000，格式 %.4f。

時間複雜度 O(n)，空間 O(1)，極其高效。

完整 C++ 參考程式碼

#include <cstdio>
#include <cmath>

int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        double ans = 0.0;
        int total = n + m;
        for (int i = 1; i < n; ++i) {
            double pos = (double)i / n * total;          // 目標索引的浮點位置
            double nearest = floor(pos + 0.5);           // 四捨五入最近整數索引
            ans += fabs(pos - nearest) / total;          // 單位圓周長下的移動距離
        }
        printf("%.4f\n", ans * 10000.0);                 // 放大至實際周長
    }
    return 0;
}

樣例驗證

常見誤區與提示

• 別忘記 i 從 1 開始：第 0 座固定為原點不動。
• 雙精度足夠：double 精度遠超 0.0001 需求。
• 圓周長 10000 只在最後乘入：中間計算全在單位圓周長下進行，避免精度損失。
• 四捨五入用 floor(x+0.5)：比 round() 更通用、無需 C99。

延伸思考

若允許新雕塑也移動，或不固定第 0 座雕塑，問題會轉化為「最小化總移動距離的最佳匹配」，可用最小費用流或動態規劃求解，複雜度顯著上升。本題巧妙利用「新雕塑位置任意」與「固定一點打破對稱」將問題線性化，是競賽中常見的幾何轉代數技巧。