关于曼哈顿距离与切比雪夫距离的转换问题
BaiBaiShaFeng
·
·
算法·理论
写这篇文章的动机？当时刷 Atcoder 的时候自信打开了一道题，只有 1600 的难度，但是愚蠢的我就是想了小半个下午，最后红温看题解才发现这个题是曼哈顿距离和切比雪夫距离的相互转化。
感觉没用，但仔细想了想似乎还挺常见的，起码我见过的比我写过的数论分块多，加上洛谷的专栏似乎搜不到什么这个 trick 的介绍和题目整理，我觉得有些必要整理一下。
这个东西真的挺有意思的。
前置知识
在开始 trick 的讲解之前，我们需要明白什么是曼哈顿距离，什么是切比雪夫距离，大家肯定常见，我就大概写一下。
曼哈顿距离
假设点 i 的坐标为 (x_i,y_i)，点 j 的坐标为 (x_j,y_j)。
点 i 和 j 的曼哈顿距离就是 \left | x_i-x_j \right | + \left | y_i-y_j \right | 。
人话就是两个横纵坐标差的和。
切比雪夫距离
假设点 i 的坐标为 (x_i,y_i)，点 j 的坐标为 (x_j,y_j)。
点 i 和 j 的切比雪夫距离就是 \max(\left | x_i-x_j \right |,\left | y_i-y_j \right |)
人话就是横纵坐标差最大的那个。
二者的转化
有的时候我们会遇到一些特殊的需求。
比如我们需要计算一大堆切比雪夫距离，而我们只能 O(n) 求，如果我们转换成方便算一大堆求和的曼哈顿距离就会方便很多很多。
先讲讲这两个是怎么变换的。
曼哈顿距离转切比雪夫距离
先说结论：将每个坐标 (x,y) 变作 (x+y,x-y) 后，原坐标的曼哈顿距离等于新坐标的切比雪夫距离，现在我们证明一下这个是对的。
我们写出来了一个美丽的曼哈顿距离：\left | x_i-x_j \right | + \left | y_i-y_j \right | 。
怎么办，我们使用初中就会的拆绝对值，把每一个情况都写出来。
那就是 \max(x_i-x_j+y_i-y_j,x_i-x_j+y_j-x_i,x_j-x_i+y_i-y_j,x_j-x_i+y_j-y_i)。
我们观察到可以将点转化为 (x+y,x-y)。
这样新图中的切比雪夫距离就是 \max(\left | (x_i+y_i)-(x_j+y_j) \right |,\left | (x_i-y_i)-(x_j-y_j) \right |)。
不难发现，这个新坐标的切比雪夫距离的两项分别对应了原坐标的曼哈顿距离的前两项。
切比雪夫距离转曼哈顿距离
还是再说结论：将每个 (x,y) 转化为 (\frac{x+y}{2},\frac{x-y}{2})，原坐标的切比雪夫距离等于新坐标的曼哈顿距离。
这个我们直接利用上边的倒推就行了。
上边有 (x,y)\to(x+y,x-y)。
设 x+y=a,x-y=b，我们要用 a,b 表示 (x,y)。
很显然 x=\frac{a+b}{2}，y=\frac{a-b}{2}。
这就出来了，不过值得注意的是我们很多时候没有办法处理这个分母，因为不方便存小数，所以一般就把结果乘上二分之一，这样记忆起来也算方便，毕竟两个都一样了。
总结
$(x,y)\to(\frac{x+y}{2},\frac{x-y}{2})$ 原坐标的切比雪夫距离等于新坐标的曼哈顿距离。
## 例题
见过的题目还不少，这边我就放几道。
### [[ABC351E] Jump Distance Sum](https://www.luogu.com.cn/problem/AT_abc351_e)
我们有 $N$ 个点，要求 $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}dis(P_i,P_j)
我们定义 $dis(P_i,P_j)$ 为从 $P_i$ 到 $P_j$ 的最小操作次数。
关于操作，我们假设现在处于 $(x,y)$，我们可以到达 $(x+1,y+1)$，$(x+1,y-1)$，$(x-1,y+1)$，$(x-1,y-1)$。
如果不可到达则值为 $0$。
首先我们想怎么计算两个点的距离，不然打暴力都做不到。
我们设 $a=\left | x_i-x_j \right |$，$b=\left | y_i-y_j \right |$。
可以抽象为 $a,b$ 两个数字，每一次同时对两个进行操作，每次对任意一个加一或减一，想将其变为零。
明显的，如果两个数的和是偶数，我们是没有办法拼出来的，所以我们选择去按照 $x+y$ 的奇偶性进行分类，这样子我们可以保证一个分类中的一定是有解的，我们在两类中统计答案。
答案是什么呢？按照以上的思路，很明显是 $\max(a,b)$。
但是我们需要对这个东西进行一堆求和，这个东西似乎不好做了。
二我们可以发现这个东西实际上就是切比雪夫距离，所以我们直接将其转化为曼哈顿距离，这样我们可以将 $x,y$ 分别计算，排个序就行。
放一下代码。
```cpp
#include <bits/stdc++.h>
using namespace std;
//参考的atcoder标程的实现
//自己做失败了...
const int MN=1e6+116;
int n, ans=0;
vector <int> vec[4];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>n;
for(int i=1,x,y; i<=n; ++i){
cin>>x>>y;
if((x+y)%2==0){
vec[0].push_back(x+y);
vec[1].push_back(x-y);
}else{
vec[2].push_back(x+y);
vec[3].push_back(x-y);
}
}
for(int i=0; i<4; ++i){
sort(vec[i].begin(),vec[i].end());
int siz=vec[i].size();
for(int j=0; j<siz; ++j){
ans+=vec[i][j]*(2*j+1-siz);
}
}
cout<<ans/2<<'\n';
return 0;
}
```
### [[TJOI2013] 松鼠聚会](https://www.luogu.com.cn/problem/P3964)
每个小松鼠的家可以用一个点 $(x,y)$ 表示,两个点的距离定义为点 $(x,y)$ 和它周围的 $8$ 个点 $(x-1,y)$，$(x+1,y)$，$(x,y-1)$，$(x,y+1)$，$(x-1,y+1)$，$(x-1,y-1)$，$(x+1,y+1)$，$(x+1,y-1)$ 距离为 $1$。
$0\le N \le 10^5$，$-10^9 \le x, y \le 10^9$。
明显这个是要求一个到其他所有点的切比雪夫距离之和最小的点。
我们还是不方便做，所以直接转曼哈顿距离。
考虑将 $x,y$ 拆开计算，我们把 $x,y$ 排好序，用 map 找这个数字的位置，最后直接算就行，比较好想就不多讲了。
这个题的答案奇大，初始值别开小了，不然会全错。
放一下代码：
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace BaiBaiShaFeng{
const int MN=1e6+116;
int n, x[MN], y[MN], cpx[MN], cpy[MN];
int sumx[MN], sumy[MN], ans=LLONG_MAX;
map <int,int> mpx, mpy;
void Read(){
cin>>n;
for(int i=1,rx,ry; i<=n; ++i){
cin>>rx>>ry;
x[i]=rx+ry; y[i]=rx-ry;
cpx[i]=x[i];
cpy[i]=y[i];
}
sort(cpx+1,cpx+n+1);
sort(cpy+1,cpy+n+1);
for(int i=1; i<=n; ++i){
mpx[cpx[i]]=i;
mpy[cpy[i]]=i;
sumx[i]=sumx[i-1]+cpx[i];
sumy[i]=sumy[i-1]+cpy[i];
}
}
int get_rangex(int l, int r){
return sumx[r]-sumx[l-1];
}
int get_rangey(int l, int r){
return sumy[r]-sumy[l-1];
}
void Do(){
for(int p=1; p<=n; ++p){
int res=0;
int posx=mpx[x[p]];
int posy=mpy[y[p]];
res+=posx*x[p]-get_rangex(1,posx);
res+=get_rangex(posx+1,n)-(n-posx)*x[p];
res+=posy*y[p]-get_rangey(1,posy);
res+=get_rangey(posy+1,n)-(n-posy)*y[p];
ans=min(ans,res);
}
}
void Print(){cout<<ans/2<<'\n';}
void Solve(){
Read(); Do(); Print();
return; //enddd
}
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
BaiBaiShaFeng::Solve();
return 0;
}
```
## 结尾
大概就是这个样子了，本人不太会讲题，所以就不多搞题上去了，我做过的相似题目会放到下边，大家有兴趣可以做一下。
[[JOISC 2021] 道路の建設案 (Road Construction) (Day2)](https://www.luogu.com.cn/problem/P7561)
[[USACO14MAR] The Lazy Cow G](https://www.luogu.com.cn/problem/P4876)
[[USACO08OPEN] Cow Neighborhoods G](https://www.luogu.com.cn/problem/P2906)
[[IOI 2007] pairs 动物对数](https://www.luogu.com.cn/problem/P4648)