HDU 4311 曼哈頓距離最小化：中位數性質與前綴和 O(n log n) 解法

題目大意

給定 n ≤ 10⁵ 個平面點，選一個點作為集合點，使所有點到該點的曼哈頓距離之和最小。集合點必須是給定點之一。

核心數學：一維中位數最小化絕對值和

對於排序數列 a₁ ≤ ... ≤ a_n，函數 f(p) = Σ |a_i - p| 在中位數處取最小值。若 p 限定在數列中，任一中位數位置元素均為最優。
曼哈頓距離可分解：|x1-x2| + |y1-y2|，x、y 獨立優化。

O(n log n) 算法流程

1. 按 x 排序，計算前綴和 prefX。對排序後位置 i 的點，其 x 方向距離和：
   sumX = x_i*(i-1) - prefX[i-1] + (prefX[n]-prefX[i]) - x_i*(n-i)。
2. 同理按 y 排序計算 sumY。
3. 每個原始點總距離 = sumX + sumY，取最小值。

C++ 代碼

#include 
using namespace std;
typedef long long LL;
struct Pt { int x, y, id; LL sum; } p[100010];
LL pref[100010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> p[i].x >> p[i].y;
            p[i].id = i; p[i].sum = 0;
        }
        // x 方向
        sort(p+1, p+n+1, [](Pt a, Pt b){ return a.x < b.x; });
        for (int i = 1; i <= n; ++i) pref[i] = pref[i-1] + p[i].x;
        for (int i = 1; i <= n; ++i) {
            int id = p[i].id;
            p[id].sum += (LL)p[i].x * (i-1) - pref[i-1];
            p[id].sum += pref[n] - pref[i] - (LL)p[i].x * (n-i);
        }
        // y 方向
        sort(p+1, p+n+1, [](Pt a, Pt b){ return a.y < b.y; });
        for (int i = 1; i <= n; ++i) pref[i] = pref[i-1] + p[i].y;
        for (int i = 1; i <= n; ++i) {
            int id = p[i].id;
            p[id].sum += (LL)p[i].y * (i-1) - pref[i-1];
            p[id].sum += pref[n] - pref[i] - (LL)p[i].y * (n-i);
        }
        LL ans = LLONG_MAX;
        for (int i = 1; i <= n; ++i) ans = min(ans, p[i].sum);
        cout << ans << '\n';
    }
    return 0;
}

複雜度

• 時間：O(n log n)（兩次排序）。
• 空間：O(n)。

總結

HDU 4311 是「曼哈頓距離最小化」的標準題（與 HDU 4312 切比雪夫距離為姊妹題）。核心模板：分解維度 → 排序+前綴和 O(1)查單點距離和 → 取最小。掌握此模板可秒殺同類幾何優化問題。