HDU 5073 Galaxy：數學期望與前綴和優化 DP

題目大意

數軸上 n 個點，每點權重 1。可移動 k 個點到任意位置。最小化 Σ d_i²，其中 d_i 為第 i 點到重心的距離。n ≤ 50000。

數學轉化

權重均為 1，重心 m = (Σ x_i) / (n-k)。目標函數：

I = Σ (x_i - m)² = Σ x_i² - 2m Σ x_i + (n-k)m²

移動 k 個點最優策略：將它們移到重心（d_i=0）。剩下 n-k 個點應為排序後的連續區間（從兩端拿掉 k 個）。

演算法

1. 排序所有點位置
2. 預計算前綴和：sum1[i] = Σ x_j, sum2[i] = Σ x_j²
3. 枚舉剩餘連續區間 [i, i+n-k-1]，用前綴和 O(1) 計算 I
4. 取最小值

完整代碼

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int M = 50010;
double x[M], x2[M];

int main() {
    int T, n, k;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; i++) scanf("%lf", &x[i]);
        double ans = 0;
        if (n != k) {
            sort(x+1, x+n+1);
            for (int i = 1; i <= n; i++) x2[i] = x[i]*x[i];
            double sum1 = 0, sum2 = 0;
            for (int i = 1; i <= n-k; i++) { sum1 += x[i]; sum2 += x2[i]; }
            double m = sum1 / (n-k);
            ans = sum2 - 2*m*sum1 + m*m*(n-k);
            for (int i = 2, j = n-k+1; j <= n; i++, j++) {
                sum1 += x[j] - x[i-1];
                sum2 += x2[j] - x2[i-1];
                m = sum1 / (n-k);
                double tmp = sum2 - 2*m*sum1 + m*m*(n-k);
                if (tmp < ans) ans = tmp;
            }
        }
        printf("%.10f\n", ans);
    }
    return 0;
}

複雜度分析

排序 O(n log n)，枚舉 O(n)，總時間 O(n log n)，空間 O(n)。