wiki - 算法小站

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

杂项

启发式合并

高精度

一些经典问题

约瑟夫环

曼哈顿距离

[[ item.c ]]

曼哈顿距离

## 前置知识，向量的旋转矩阵
![](/media/content_img/vectorRotate.png)

## 曼哈顿距离
### 关于曼哈顿距离求 min-max
#### 曼哈顿距离转切比雪夫距离
![](/media/content_img/ManhaToCheby.png)

```math
\displaystyle
(x, y) \to (y + x, y - x) \\
\quad \\
|x_1 - x_2| + |y_1 - y_2| = \max(|x_1' - x_2'|, |y_1' - y_2'|) \\
= \max(| (y_1 + x_1) - (y_2 + x_2) |, |(y_1 - x_1) - (y_2 - x_2)|)
```

#### 一些应用
**[3102. 最小化曼哈顿距离](https://leetcode.cn/problems/minimize-manhattan-distances/description/)**
**问题描述**
给定若干点，返回移除一个点后，任意两点之间曼哈顿最大距离，我们要最小化这个最大距离

**算法分析**
通过曼哈顿距离转切比雪夫距离之后，可以枚举删除哪个点，计算答案之后，再还原现场，把点加回来
假设说枚举$$(x_0, y_0)$$，删点通过`set`就很容易做到，怎么让剩下的点曼哈顿距离最大呢？
实际上，通过$$\max(|x_1 - x_2|, |y_1 - y_2|)$$，可以考虑$$X, Y$$两个维度**单独来看**

只需要考虑所有**切比雪夫转化之后**的$$x$$的最大值$$xmax$$，以及最小值$$xmin$$
以及$$ymax, ymin$$，$$\max(xmax - xmin, ymax - ymin)$$即可，分别维护$$X, Y$$两个有序集合即可

#### 算法春季联赛
**[选择配送](https://acm.hdu.edu.cn/contest/problem?cid=1152&pid=1010)**
**问题描述**
给定$$n$$个客户，再给定$$m$$个快递站，要求你选择一个快递站，求出从这个站点到所有客户的曼哈顿距离的最大值
然后我们要最小化这个最大值

**算法分析**
不难发现，我们应该枚举所有的快递站，假设说枚举的快递站是$$(x_0, y_0)$$

考虑将其转化成切比雪夫距离之后，快递站的坐标是$$(x_0, y_0)$$，`min-max`问题，转化成切比雪夫之后
可以将$$x, y$$单独考虑，之后再求`max`

我们要求什么呢？实际上是$$\forall j, \max_j: \quad \max(|x_0 - x_j|, |y_0 - y_j|)$$
同样，我们把客户的坐标，转化成**切比雪夫距离坐标**之后，分别扔到$$X, Y$$两个有序集合中

这样我们就可以知道`xmax, xmin, ymax, ymin`，分类讨论
```bash
对于 x 这一维
x0 - xmin
xmax - x0

对于 y 这一维
y0 - ymin
ymax - y0
```
以上四个值，求一个$$\max$$，再和`ans`取$$\min$$即可

#### 总结

实际上，曼哈顿距离转切比雪夫距离，是因为$$\max(|x_i - x_j|, |y_i - y_j|)$$，关于$$x, y$$是**独立的**
这样我们可以独立地考虑$$x, y$$，转化成`min-max`的问题

### 关于曼哈顿距离的求和
曼哈顿距离的形式$$\sum |x_i - x_j| + |y_i - y_j|$$，对于求和而言是方便的，因为$$\sum$$
对于$$x$$和$$y$$是**独立的**，可以只考虑$$x$$这一维的求和

在考虑求和问题的时候，切比雪夫距离往往转化成曼哈顿距离更方便

#### 切比雪夫转曼哈顿距离
**[E - Jump Distance Sum](https://atcoder.jp/contests/abc351/tasks/abc351_e)**
**问题描述**
给定`n`个点，每个点只能左上，左下，右上，右下移动，定义`dist(x, y)`为从$$x to y$$的最短步数
如果不能到达，则为`0`，求
```math
\displaystyle
\sum_{i = 1}^{n - 1} \sum_{j = i+1}^{n} dist(P_i, P_j)
```

**算法分析**
> 先考虑什么情况下不可达

注意到$$(x, y)$$可以走到$$(x+1, y+1), (x-1, y+1), (x+1, y-1), (x-1, y-1)$$
有什么特点呢？$$(x, y)$$能够到达的点，一定和$$x+y$$同奇偶

我们可以根据奇偶性分类，同一个集合中的点，一定是能够相互到达的，分开来计算

> 考虑原问题描述的是什么？

实际上，原问题的距离是求$$(P_i, P_j)$$在**坐标系顺时针旋转 45 之后**的**曼哈顿距离**
也就是$$(P_i, P_j)$$的**切比雪夫距离**，此时的$$P(x, y)$$定义为**切比雪夫坐标**
切比雪夫坐标下，切比雪夫距离是$$\max(|x_i - x_j|, |y_i - y_j|)$$，$$x, y$$不独立，不好计算

考虑将**切比雪夫坐标**转为正常的直角坐标（称为**曼哈顿坐标**），然后求曼哈顿距离
```math
\displaystyle
\begin{cases}
y'+x' = x \\
y'-x' = y
\end{cases} \quad 
\begin{cases}
y' = \dfrac{x + y}{2} \\
x' = \dfrac{x - y}{2}
\end{cases}
```
其中$$(x, y)$$是原来的坐标，$$(x', y')$$是曼哈顿坐标，令$$x = x', y = y'$$之后
求曼哈顿距离即可，另外值得注意的是，这里$$/2$$会有精度误差，因为是求和，可以算完答案后，再$$/2$$

最后考虑怎么计算答案，$$x, y$$两个维度，在**曼哈顿距离求和**中，可以独立统计
对$$x$$进行排序，枚举$$x_i$$，假设说`m = X.size()`
```bash
x[i+1] - x[i]
x[i+2] - x[i]
......
......
x[m-1] - x[i]
```
```math
\displaystyle
\left( \sum_{j = i+1}^{m-1} x_j \right) - (m - 1 - i) \cdot x_i
```
前缀和即可方便计算，`Y`同理

#### Codeforces Round 1038
**[C. Manhattan Pairs](https://codeforces.com/contest/2122/problem/C)**
给定$$n$$个点，`n`为偶数，你现在需要为这`n`个点，选择不同的点**两两配对**，最终形成$$n/2$$对
对于每一对$$(a_i, b_i)$$，我们需要最大化
```math
\sum_{i = 1}^{n/2}|x(a_i) - x(b_i)| + |y(a_i) - y(b_i)|
```
求配对方案数，可能会有多个满足条件的结果，输出任意一个

**算法分析**
如果是任意几对两两配对，那么就是$$(a, b)$$的最大权匹配问题，权值为**两个点的曼哈顿距离**
但这里给定的是$$\sum$$最优的方案，能不能从这里入手？
遇到这种问题，我们猜想，每一对不一定最优，但是可以保证`sum`最优，这怎么做呢？

注意到，因为是$$n/2$$对两两匹配，如果只看`x`这个维度的话，这$$n$$个$$x$$坐标**都要利用上**
在表达式$$|x_i - x_j|$$中，我们需要选出$$n / 2$$个$$+x$$，$$n / 2$$个$$-x$$
这个怎么选呢？不难发现，这样的方案是唯一的

对`x`坐标排序，然后前一半的贡献都必须是`-1`，后一半的贡献都必须是`+1`
（否则的话，就会出现`-(较大的数)  +(较小的数) < 0`，对答案的贡献变差）

注意到我们并不关注每一对是否最优，而只关注$$\sum$$最优，那么`+`的一半和`-`的一半，
任意配对，无所谓顺序，都是不影响$$\sum |x_i - x_j|$$的值的，反正都是大的减小的
```bash
对答案 X 这一维的贡献，总的是
(后半部分的 x 的和) - (前半部分 x 的和)
```

> 注意到曼哈顿距离求和，X, Y 两个维度可以分开计算

把前半部分记为$$L$$，后半部分记为$$R$$，那既然$$L, R$$中的元素配对，无所谓$$x$$的顺序
那么我们只需要考虑`Y`这一维了
只要让`L`中$$y$$最小的，和`R`中$$y$$最大的配对就可以
这个很简单了，维护$$L$$集合关于$$y$$的**小根堆**，同时维护$$R$$集合关于$$y$$的**大根堆**
堆中存二元组`(y, id)`即可

看完文章有啥想法

算法小站

wiki 主题

杂项

曼哈顿距离

目录