HDU 5073 Galaxy 貪心 + 前綴和 最小轉動慣量

問題物理模型

n 個質點（質量 1）在數軸位置 x[i]，繞質心旋轉。可移動 ≤k 個質點到任意位置（疊加允許）。最小化轉動慣量 I = Σ (x_i - x_cm)²。

關鍵洞察

1. 移動的質點最佳位置 = 新質心位置（貢獻為 0）
2. 保留的 n-k 個質點在排序後必須連續（否則中間有間隙會增加慣量）
3. 質心 = 保留質點位置平均值

算法流程

1. 位置排序
2. 預計算前綴和 sum[i] = Σ x[j] 和平方和 sum2[i] = Σ x[j]²
3. 枚舉保留區間 [L, R]（長度 n-k）：
   • cnt = n-k
   • cm = (sum[R]-sum[L-1]) / cnt
   • I = (sum2[R]-sum2[L-1]) - 2*cm*(sum[R]-sum[L-1]) + cnt*cm²
4. 取最小 I

代碼實現

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, k; cin >> n >> k;
        vector<long long> x(n+1);
        for (int i = 1; i <= n; ++i) cin >> x[i];
        sort(x.begin()+1, x.end());

        if (n <= k || n - k == 1) { cout << "0\n"; continue; }

        vector<long long> sum(n+1), sum2(n+1);
        for (int i = 1; i <= n; ++i) {
            sum[i] = sum[i-1] + x[i];
            sum2[i] = sum2[i-1] + x[i]*x[i];
        }

        int keep = n - k;
        double ans = 1e100;
        for (int L = 1; L + keep - 1 <= n; ++L) {
            int R = L + keep - 1;
            double cm = (sum[R] - sum[L-1]) * 1.0 / keep;
            double I = (sum2[R] - sum2[L-1]) - 2*cm*(sum[R] - sum[L-1]) + keep*cm*cm;
            ans = min(ans, I);
        }
        printf("%.9f\n", ans);
    }
    return 0;
}

複雜度與精度

• 排序 O(n log n)，枚舉 O(n)，總 O(n log n)
• 雙精度浮點足夠（要求 1e-9 相對/絕對誤差）
• 初始 ans 設大值（非 0）避免 WA