🧠 题目解析

🔍 问题描述：

给定若干个居民楼的坐标 (x, y)，要求选择一个点 (x0, y0) 作为机器人服务中心的位置，使得所有居民楼到该中心的曼哈顿距离总和最小。

曼哈顿距离公式：

$$\text{distance} = |x_1 - x_2| + |y_1 - y_2|$$

---

✅ 解法思路（贪心 + 中位数）

这是一个经典的中位数选址问题。在曼哈顿距离下，使总距离最小的最佳点是：

• x 坐标的中位数
• y 坐标的中位数

这是因为：

• 在一维空间中，要使 $\sum |x_i - x_0|$ 最小，$x_0$ 应取数据集的中位数。
• 所以我们可以分别处理 x 和 y 坐标。

---

💻 程序补全

n = int(input("请输入居民楼总数："))
hx = []
hy = []

for i in range(n):
    x, y = map(int, input("请输入居民楼的x和y坐标：").split(","))
    hx.append(x)
    hy.append(y)

hx = sorted(hx)   # ① 对x坐标排序
hy = sorted(hy)   # ② 对y坐标排序

if n % 2 == 0:    # 偶数情况，取中间两个数的平均值
    sn = int(n / 2)
    x0 = int((hx[sn] + hx[sn - 1]) / 2)
    y0 = int((hy[sn] + hy[sn - 1]) / 2)
else:             # 奇数情况，取中间那个数
    sn = int((n - 1) / 2)
    x0 = hx[sn]     # ③ 取x坐标的中位数
    y0 = hy[sn]     # ④ 取y坐标的中位数

sumx = 0
sumy = 0
for j in hx:
    dx = abs(x0 - j)
    sumx += dx
for k in hy:
    dy = abs(y0 - k)
    sumy += dy

print("选址点的坐标是：(%d,%d)" % (x0, y0))
print("选址到各楼的累计距离是：", sumx + sumy)

---

📌 贪心策略的数学原理详解

🎯 目标函数

我们要最小化的是：

$$\sum_{i=1}^{n} |x_i - x_0| + |y_i - y_0|$$

由于曼哈顿距离是可分的（即横纵坐标互不影响），我们可以将目标函数拆分为两部分：

$$f(x_0, y_0) = \sum_{i=1}^{n} |x_i - x_0| + \sum_{i=1}^{n} |y_i - y_0| $$

所以我们可以分别对 x 和 y 求最优解。

---

🧮 数学证明：为什么中位数最优？

定义：设有一组有序实数 $x_1 \leq x_2 \leq \cdots \leq x_n$

定义函数：

$$f(x_0) = \sum_{i=1}^{n} |x_i - x_0|$$

我们的目标是找到使 $f(x_0)$ 最小的 $x_0$。

---

✳️ 情况一：当 $n$ 是奇数

令 $m = \frac{n+1}{2}$，则 $x_m$ 是中位数。

• 当 $x_0 < x_m$ 时，每向右移动一点，左边的点减少贡献，右边的点增加贡献；
• 因为左边点比右边少，整体上升；
• 同理，当 $x_0 > x_m$ 时，也会导致总和增大；
• 所以，只有当 $x_0 = x_m$ 时，总和最小。

✅ 所以此时中位数是最优解。

---

✳️ 情况二：当 $n$ 是偶数

令 $m_1 = \frac{n}{2}, m_2 = \frac{n}{2} + 1$

• 此时，任意 $x_0 \in [x_{m_1}, x_{m_2}]$ 的值都会得到相同的最小值；
• 通常取这个区间的中点作为代表：$x_0 = \frac{x_{m_1} + x_{m_2}}{2}$

✅ 所以这时取中间两个数的平均值最优。

---

📈 总结贪心策略的正确性

• 曼哈顿距离可分解为横向和纵向之和；
• 每个方向上，中位数能使绝对差之和最小；
• 所以二维问题可以通过分别取 x 和 y 的中位数来解决；
• 这是一种典型的贪心策略，且具有数学保证的最优性。

---

📝 示例运行

输入：

请输入居民楼总数：5
请输入居民楼的x和y坐标：1,2
请输入居民楼的x和y坐标：3,4
请输入居民楼的x和y坐标：5,6
请输入居民楼的x和y坐标：7,8
请输入居民楼的x和y坐标：9,10

输出：

选址点的坐标是：(5,6)
选址到各楼的累计距离是： 16

---

📚 结语

这道题是一个非常经典的贪心算法应用，其背后有坚实的数学支撑 —— 即在一维空间中，中位数是最小化绝对差之和的最优解。

📘 中位数（Median）教程

✅ 什么是中位数？

中位数是一组数据中间位置的数值。它是将一组数据从小到大排列后，位于中间位置的那个数。与平均数不同，中位数不受极端值的影响，更适合描述偏态分布的数据中心趋势。

---

📌 中位数的计算方法

步骤如下：

1. 将所有数据按升序（从小到大）排列。
2. 判断数据个数 $n$ 的奇偶性：
   • 如果是奇数个数据，中位数就是正中间那个数。
   • 如果是偶数个数据，中位数是中间两个数的平均值。

---

🔢 数学公式表示

设数据为：$x_1, x_2, \dots, x_n$，且已排序。

情况一：当 $n$ 是奇数时

$$\text{中位数} = x_{\frac{n+1}{2}}$$

情况二：当 $n$ 是偶数时

$$\text{中位数} = \frac{x_{\frac{n}{2}} + x_{\frac{n}{2} + 1}}{2} $$

---

🧮 示例讲解

示例 1：奇数个数据

数据：[3, 5, 1, 7, 2]

步骤：

1. 排序：[1, 2, 3, 5, 7]
2. $n = 5$，是奇数
3. 中间位置：第 $\frac{5+1}{2} = 3$ 个数 → 3

✅ 中位数 = 3

---

示例 2：偶数个数据

数据：[4, 6, 2, 8]

步骤：

1. 排序：[2, 4, 6, 8]
2. $n = 4$，是偶数
3. 中间两个数：第 $\frac{4}{2} = 2$ 和 第 $\frac{4}{2} + 1 = 3$ 个数 → 4 和 6
4. 平均值：$\frac{4 + 6}{2} = 5$

✅ 中位数 = 5

---

📈 中位数的优点

特点	描述
不受极端值影响	即使有极大或极小值，中位数依然稳定
易于理解	不需要复杂计算，直观反映数据中心位置
适用于有序数据	如等级评分、考试成绩等

---

💡 应用场景

• 教育统计：学生考试成绩分析
• 房地产：房价中位数更能反映真实市场水平
• 收入调查：避免高收入拉高平均值，更公平反映“典型”收入
• 数据清洗：去除异常值时常用中位数代替缺失值

曼哈顿距离（Manhattan Distance），也被称为城市街区距离、L1距离或绝对值距离，是一种用于度量几何空间中两点之间距离的度量方式。它定义为两个点在标准坐标系上的绝对轴距之和。

对于二维空间中的两个点 $P_1 = (x_1, y_1)$ 和 $P_2 = (x_2, y_2)$，它们之间的曼哈顿距离 $D$ 计算公式如下：

$$D = |x_1 - x_2| + |y_1 - y_2|$$

这里，$|\cdot|$ 表示绝对值。这意味着从一个点到另一个点的距离是沿着水平和垂直方向移动的总和，而不是直接的直线距离（欧几里得距离）。

曼哈顿距离的名字来源于纽约市曼哈顿区的街道布局，那里的道路网络形成了一个规则的网格，因此在这个区域内的任意两点之间的最短路径就是沿着东西向和南北向的道路行走的总和，就像乘坐出租车时的行驶路线一样，因此有时也称为“出租车距离”。

这种距离度量方法在多种应用中都非常有用，比如在机器学习算法（如k-近邻算法）、棋盘游戏（如国际象棋中的国王走法）、图像处理以及城市规划等方面。在这些场景中，由于实际限制，往往只能沿特定方向行进，这时使用曼哈顿距离就非常合适。

在编程和数学中，两点之间的距离公式取决于你使用的距离度量方式。最常用的有以下几种：

---

📌 1. 欧几里得距离（Euclidean Distance）

这是我们在几何中最常用的距离公式。

公式：

对于两个点 $A(x_1, y_1)$ 和 $B(x_2, y_2)$，欧几里得距离为：

$$\text{distance} = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $$

Python 实现：

import math

x1, y1 = 1, 2
x2, y2 = 4, 6
distance = math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
print("欧几里得距离：", distance)

---

📌 2. 曼哈顿距离（Manhattan Distance）

常用于网格路径问题、城市街区行走等场景。

公式：

$$\text{distance} = |x_2 - x_1| + |y_2 - y_1|$$

Python 实现：

x1, y1 = 1, 2
x2, y2 = 4, 6
distance = abs(x2 - x1) + abs(y2 - y1)
print("曼哈顿距离：", distance)

---