關(guān)于曼哈頓距離和切比雪夫距離的關(guān)系

寫這篇文章的動機？當(dāng)時刷 Atcoder 的時候自信打開了一道題，只有 1600 的難度，但是愚蠢的我就是想了小半個下午，最后紅溫看題解才發(fā)現(xiàn)這個題是曼哈頓距離和切比雪夫距離的相互轉(zhuǎn)化。

感覺沒用，但仔細想了想似乎還挺常見的，起碼我見過的比我寫過的數(shù)論分塊多，加上洛谷的專欄似乎搜不到什么這個 trick 的介紹和題目整理，我覺得有些必要整理一下。

這個東西真的挺有意思的。

前置知識

在開始 trick 的講解之前，我們需要明白什么是曼哈頓距離，什么是切比雪夫距離，大家肯定常見，我就大概寫一下。

曼哈頓距離

假設(shè)點 $i$ 的坐標(biāo)為 $(x_i,y_i)$，點 $j$ 的坐標(biāo)為 $(x_j,y_j)$。

點 $i$ 和 $j$ 的曼哈頓距離就是 $\left | x_i-x_j \right | + \left | y_i-y_j \right | $。

人話就是兩個橫縱坐標(biāo)差的和。

切比雪夫距離

假設(shè)點 $i$ 的坐標(biāo)為 $(x_i,y_i)$，點 $j$ 的坐標(biāo)為 $(x_j,y_j)$。

點 $i$ 和 $j$ 的切比雪夫距離就是 $\max(\left | x_i-x_j \right |,\left | y_i-y_j \right |)$

人話就是橫縱坐標(biāo)差最大的那個。

二者的轉(zhuǎn)化

有的時候我們會遇到一些特殊的需求。

比如我們需要計算一大堆切比雪夫距離，而我們只能 $O(n)$ 求，如果我們轉(zhuǎn)換成方便算一大堆求和的曼哈頓距離就會方便很多很多。

先講講這兩個是怎么變換的。

曼哈頓距離轉(zhuǎn)切比雪夫距離

先說結(jié)論：將每個坐標(biāo) $(x,y)$ 變作 $(x+y,x-y)$ 后，原坐標(biāo)的曼哈頓距離等于新坐標(biāo)的切比雪夫距離，現(xiàn)在我們證明一下這個是對的。

我們寫出來了一個美麗的曼哈頓距離：$\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)$。

我們觀察到可以將點轉(zhuǎn)化為 $(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 |)$。

不難發(fā)現(xiàn)，這個新坐標(biāo)的切比雪夫距離的兩項分別對應(yīng)了原坐標(biāo)的曼哈頓距離的前兩項。

切比雪夫距離轉(zhuǎn)曼哈頓距離

還是再說結(jié)論：將每個 $(x,y)$ 轉(zhuǎn)化為 $(\frac{x+y}{2},\frac{x-y}{2})$，原坐標(biāo)的切比雪夫距離等于新坐標(biāo)的曼哈頓距離。

這個我們直接利用上邊的倒推就行了。

上邊有 $(x,y)\to(x+y,x-y)$。

設(shè) $x+y=a,x-y=b$，我們要用 $a,b$ 表示 $(x,y)$。

很顯然 $x=\frac{a+b}{2}$，$y=\frac{a-b}{2}$。

這就出來了，不過值得注意的是我們很多時候沒有辦法處理這個分母，因為不方便存小數(shù)，所以一般就把結(jié)果乘上二分之一，這樣記憶起來也算方便，畢竟兩個都一樣了。

總結(jié)

$(x,y)\to(x+y,x-y)$ 原坐標(biāo)的曼哈頓距離等于新坐標(biāo)的切比雪夫距離。

$(x,y)\to(\frac{x+y}{2},\frac{x-y}{2})$ 原坐標(biāo)的切比雪夫距離等于新坐標(biāo)的曼哈頓距離。

例題

見過的題目還不少，這邊我就放幾道。

[ABC351E] Jump Distance Sum

我們有 $N$ 個點，要求 $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}dis(P_i,P_j)$

$P_i$ 指的是第 $i$ 個點。

我們定義 $dis(P_i,P_j)$ 為從 $P_i$ 到 $P_j$ 的最小操作次數(shù)。

關(guān)于操作，我們假設(shè)現(xiàn)在處于 $(x,y)$，我們可以到達 $(x+1,y+1)$，$(x+1,y-1)$，$(x-1,y+1)$，$(x-1,y-1)$。

如果不可到達則值為 $0$。

首先我們想怎么計算兩個點的距離，不然打暴力都做不到。

我們設(shè) $a=\left | x_i-x_j \right |$，$b=\left | y_i-y_j \right |$。

可以抽象為 $a,b$ 兩個數(shù)字，每一次同時對兩個進行操作，每次對任意一個加一或減一，想將其變?yōu)榱恪?/p>

明顯的，如果兩個數(shù)的和是偶數(shù)，我們是沒有辦法拼出來的，所以我們選擇去按照 $x+y$ 的奇偶性進行分類，這樣子我們可以保證一個分類中的一定是有解的，我們在兩類中統(tǒng)計答案。

答案是什么呢？按照以上的思路，很明顯是 $max(a,b)$。

但是我們需要對這個東西進行一堆求和，這個東西似乎不好做了。

二我們可以發(fā)現(xiàn)這個東西實際上就是切比雪夫距離，所以我們直接將其轉(zhuǎn)化為曼哈頓距離，這樣我們可以將 $x,y$ 分別計算，排個序就行。

放一下代碼。

#include <bits/stdc++.h>
using namespace std;
//參考的atcoder標(biāo)程的實現(xiàn)
//自己做失敗了...
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] 松鼠聚會

每個小松鼠的家可以用一個點 $(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$。

明顯這個是要求一個到其他所有點的切比雪夫距離之和最小的點。

我們還是不方便做，所以直接轉(zhuǎn)曼哈頓距離。

考慮將 $x,y$ 拆開計算，我們把 $x,y$ 排好序，用 map 找這個數(shù)字的位置，最后直接算就行，比較好想就不多講了。

這個題的答案奇大，初始值別開小了，不然會全錯。

放一下代碼：

#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;
}