哈基米南北路多

结论在下面帆学长的题解里，形象的说，可以把这些点的纵坐标放进一条一维轴中，指定一个点，则曼哈顿距离则是这些点到指定点的距离和，那么这个点定在最左点和最右点之间（因为超出范围产出的多余距离一定会导致结果不是最优解） 下面看两种情况 1.元素数量为奇数 将指定点设为在最中间的点可省去到此点的距离，而其他的点距离和即为从中间往两边数左右各一个数的距离之和 2.元素数量为偶数 大体和奇数情况一致，但目标点可以为中间两点之间的任意点，结果都是最优解不变

参考代码（python）

from sys import stdin,setrecursionlimit
from math import inf,ceil,sqrt
from collections import Counter,deque

n,x=[int(_) for _ in stdin.readline().split()]
d=[[int(_) for _ in stdin.readline().split()] for i in range(n)]
d.sort(key=lambda x:x[1])
ans=sum(abs(x-d[i][0]) for i in range(n))
for i in range(n // 2):
    ans += d[n-i-1][1] - d[i][1]
print(ans)

哈基米南北路多

这是一个经典结论：

对任意一组数 ( $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:两个取平均数和取端点一样不影响，无需算平均