哈基米南北路多

这是一个经典结论：

对任意一组数 ( $y_1, y_2, \dots, y_n$ )， 使函数 ( $f(y) = \sum |y_i - y|$ ) 最小的 ( y ) 为所有 ( $y_i$ ) 的中位数。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long X;
    cin >> n >> X;

    vector<long long> ys(n);
    long long sumX = 0;

    for (int i = 0; i < n; i++) {
        long long xi, yi;
        cin >> xi >> yi;
        sumX += llabs(xi - X); // 横向距离
        ys[i] = yi;
    }

    sort(ys.begin(), ys.end());
    long long median = ys[n / 2]; // 中位数
    long long sumY = 0;

    for (int i = 0; i < n; i++) {
        sumY += llabs(ys[i] - median);
    }

    cout << sumX + sumY << "\n";
    return 0;
}

一句话总结：

“哈基米走南北路，走到中位数那就是最短的路。”

猜你想问

Q:中位数有两个怎么办 A:两个取平均数和取端点一样不影响，无需算平均