HDU 4311 Meeting Point：曼哈頓距離最小化的中位數性質與前綴和優化

題目大意

給定 n ≤ 10⁵ 個點，選一個點作為集合點，使所有點到該點的曼哈頓距離之和最小。曼哈頓距離：|x1-x2| + |y1-y2|。集合點必須是給定點之一。

數學性質：中位數最小化絕對值和

對於一維數列 a₁ ≤ a₂ ≤ ... ≤ a_n，函數 f(p) = Σ |a_i - p| 在 p 為中位數時取得最小值。
若限定 p 必須是數列中的元素，則任意中位數位置的元素均為最優解。

O(n log n) 算法：排序 + 前綴和

1. 分別按 x、y 排序，記錄原始索引。
2. 計算前綴和 prefX[i] = Σ_{j=1..i} x_j。
3. 對排序後位置 i 的點，其作為集合點時的 x 方向距離和：
   sumX = x_i*(i-1) - prefX[i-1] + (prefX[n]-prefX[i]) - x_i*(n-i)。
4. 同理計算 sumY，總和 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 是「曼哈頓距離最小化」的標準題。核心洞察：曼哈頓距離可分解為 x/y 兩獨立一維問題，各自中位數最優。前綴和技巧將單點查詢優化至 O(1)，整體 O(n log n)。同模板解決 HDU 4312（切比雪夫距離轉曼哈頓）、Codeforces 幾何優化問題。