数学严格证明

在一维情境中，假设我们有一组点 $a_1, a_2, \dots, a_n$，我们想找到一个点 $x$ 使得总距离 $\sum_{i=1}^n |a_i - x|$ 最小化。

思考过程

1. 代价函数: 设距离总和函数为 $f(x) = \sum_{i=1}^n |a_i - x|$。

2. 单调性: 当我们从左向右移动点 $x$，即增加 $x$ 的值时，离 $x$ 左侧的点 $a_i$ 的距离 $|a_i - x|$ 增加，离 $x$ 右侧的点 $a_i$ 的距离 $|a_i - x|$ 减少。

3. 关键点：考虑 $x$ 跨过某个点 $a_j$ 时的函数变化。特别在 $x=a_j$ 时，所有小于等于 $a_j$ 的点 $|a_i - x|$ 减小或不变，所有大于 $a_j$ 的点 $|a_i - x|$ 增加。若 $x$ 从 $a_j - \epsilon$ (一个小量 $\epsilon$) 移动到 $a_j + \epsilon$，如果左边点的数量多于右边点的数量，$f(x)$ 的值将增加；反之则减少。因此，将 $x$ 置于左右点数量相等的地方（或尽可能平衡的地方）是有利的。

断点

由于 $|a_i - x|$ 是 V 形，其最小值发生在 $a_i = x$ 时，因此寻找最小化 $f(x)$ 的点就是寻找中位数

严谨证明

要使 $\sum_{i=1}^n |a_i - x|$ 达到最小，关键在于 $x$ 的选择。考虑下面的两种情况：

• 当 $n$ 是奇数时，中位数存在且唯一，设为 $a_k$。在 $a_k$ 处，距其左侧的点数等于距其右侧的点数。
• 当 $n$ 是偶数时，有两个中位数 $a_{n/2}$ 和 $a_{n/2 + 1}$。在此范围内任何 $x \in [a_{n/2}, a_{n/2 + 1}]$ 使得损失函数不变，即所有这些点都可以作为最小化曼哈顿距离的解。

对于两种情况，选择中位数 (或中位数区间任意一个点) 显然最小化了从 $x$ 到所有点 $\{a_i\}$ 的曼哈顿距离。

引用：

• 如果将 $x$ 移动到既非左中位数也非右中位数的其他位置，则至少有一侧将有更多的点会导致距离之和增加，因为距离增加部分无法通过另一侧距离减少来完全抵消。

通过以上证明，中位数是曼哈顿距离问题中最优解的关键所在。对于二维问题（曼哈顿距离中），该结论可以分别在 $x$ 轴和 $y$ 轴独立应用。因此，对于 $(x_i, y_i)$，分别求 $x$ 和 $y$ 的中位数即为最优解。

中位数

n = int(input()) # 输入上班族人数 n

X = [] # 用于存放所有上班族的工作地点横坐标
Y = [] # 用于存放所有上班族的工作地点纵坐标

# 读取所有上班族的工作地点坐标，并添加到X和Y列表中
for i in range(n):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)

# 对X和Y列表进行排序，以便后续计算中位数
X = sorted(X)
Y = sorted(Y)

# 计算X和Y的中位数
# 当n是奇数时，中位数为中间的一个点
# 当n是偶数时，任何位于两个中间点之间的点作为最优点都会有相同的距离和，
# 用索引 n//2 可以直接获取中位位置的值
medianX = X[n // 2]
medianY = Y[n // 2]

# 使用中位数计算所有点到中位数的距离和
# 这是因为曼哈顿距离在一维中以中位数为最优聚集点
dist_sum = sum(abs(i - medianX) for i in X) + sum(abs(i - medianY) for i in Y)

print(dist_sum) # 输出最小的距离和

稍微给个感性一点的证明。

对于每一个点集 $list$ ，要使某个点 $p(x,y)$ , 要使曼哈顿距离最小，此时可以将二维分开看待。

对于每个维度，如 $x$ ，如果他在中位数的左边，我们将 $x+=1$ , 则有一半以上的曼哈顿距离 -1 ，另外不到一半的曼哈顿距离 +1，总距离是减小的。

所以，当每个维度的坐标都是中位数的时候，曼哈顿距离是最小的。

不是很严谨，勿喷

n = int(input())
x = []
y = []
for _ in range(n):
    x1,y1 = map(int, input().split())
    x += [x1]
    y += [y1]

x = sorted(x)
y = sorted(y)
ans = 0
if (n%2):
    for i in x:
        ans += abs(i-x[n//2])
    for i in y:
        ans += abs(i-y[n//2])
else :
    for i in x:
        ans += abs(i - x[n // 2])
    for i in y:
        ans += abs(i - y[n // 2])

print(ans)