曼哈顿距离的题

### 关于曼哈顿距离的算法题练习 以下是几个经典的涉及曼哈顿距离的算法题目及其背景介绍： #### 题目一：OJ 第1005题 —— 计算曼哈顿距离 此题要求输入两个点的坐标 `(x1, y1)` 和 `(x2, y2)`，并计算它们之间的曼哈顿距离。公式为 `|x1 - x2| + |y1 - y2|`[^1]。 ```python def manhattan_distance(x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2) # 测试样例 print(manhattan_distance(1, 2, 4, 6)) # 输出应为7 ``` --- #### 题目二：LeetCode 曼哈顿距离问题 在 LeetCode 的某些题目中会涉及到曼哈顿距离的应用场景。例如给定一组点集合，找到某个特定条件下的最优解。具体实现可能需要遍历所有点对来计算每一对点间的曼哈顿距离[^2]。 ```python from itertools import combinations def total_manhattan_distances(points): total = 0 for (x1, y1), (x2, y2) in combinations(points, 2): total += abs(x1 - x2) + abs(y1 - y2) return total points = [(1, 2), (3, 4), (5, 6)] print(total_manhattan_distances(points)) # 输出总曼哈顿距离 ``` --- #### 题目三：洛谷 P3964 [TJOI2013] 松鼠聚会 这是一道典型的多维曼哈顿距离应用题。题目描述了一群松鼠分布在二维平面的不同位置上，目标是最小化所有松鼠移动到某一点所需的总曼哈顿距离之和[^3]。 解决方法通常基于 **分治策略** 或者通过分析曼哈顿距离性质得出结论：最终的目标点通常是所有点坐标的中位数位置。 ```python import statistics def min_total_distance(points): xs = sorted([point[0] for point in points]) ys = sorted([point[1] for point in points]) median_x = statistics.median(xs) median_y = statistics.median(ys) total_distance = sum(abs(point[0] - median_x) + abs(point[1] - median_y) for point in points) return int(total_distance) points = [[1, 1], [2, 2], [3, 3]] print(min_total_distance(points)) ``` --- #### 题目四：POJ 2926 Requirements 多维曼哈顿最远点对 该问题是更高维度上的扩展版本，即考虑 n 维空间中的多个点，并找出任意两点多维曼哈顿距离的最大值。 由于暴力枚举复杂度较高，在实际比赛中往往采用一些优化技巧或者数据结构加速查找过程。 ```python def max_multidimensional_mhd(points): dimensions = len(points[0]) # 假设所有点具有相同维度 max_dist = float('-inf') for i in range(len(points)): for j in range(i + 1, len(points)): dist = sum(abs(a - b) for a, b in zip(points[i], points[j])) if dist > max_dist: max_dist = dist return max_dist points = [ [1, 2, 3], [4, 5, 6], [-1, -2, -3] ] print(max_multidimensional_mhd(points)) # 打印最大曼哈顿距离 ``` --- #### 题目五：牛客网第八场多校赛 D 距离（三维 BIT） 本题是一个更复杂的三维曼哈顿最近点对问题，需要用到高级数据结构如树状数组（Binary Indexed Tree, BIT）。核心思路是对每个维度分别处理前缀和后缀信息，从而快速查询满足条件的最佳匹配点。 代码实现较为复杂，建议深入研究相关资料后再尝试编码。 --- ### 总结 上述列举了几类不同难度级别的曼哈顿距离相关题目，涵盖了基础概念理解以及高阶优化技术等多个层面的知识点。希望这些例子能够帮助您更好地掌握这一领域的内容！