文章目录曼哈顿距离与勤奋音响距离及其相互转换1 .算法分析1.1曼哈顿距离1.2与勤奋音响距离1.3的关系1.4有用性2 .典型例题

曼哈顿距离和勤奋的音响距离及其相互转换1 .算法分析1.1曼哈顿距离

定义平面空间内存在两点，它们的坐标为[x1，y1]、[x2，y2][x_1，y_1，x_2，y_2][x1，y1]、[x2

(dIs=) x1x2) ) y1y2 ) dis=|x _ 1x _2||y _ 1y _2| dis=(x1x2) ) y1y2 ()

即两点横纵轴之差之和

煮个栗子

如图所示，图中a、b

两点的曼哈顿距离=4 3=7

1.2勤奋的声学距离定义平面空间内存在两点，它们的坐标为[x1，y1]、[x2，y2][x_1，y_1，x_2，y_2][x1，y1]

dIs=max(x1

x 2 ∣ , ∣ y 1 − y 2 ∣ ) dis=max(|x_1−x_2|,|y_1−y_2|) dis=max(∣x1​−x2​∣,∣y1​−y2​∣)

即两点横纵坐标差的最大值

再煮个栗子

dis=4

1.3 两者之间的关系

两者的定义看上去好像毛线关系都没有，但实际上，这两种距离可以相互转化！ 我们考虑最简单的情况，在一个二维坐标系中，设原点为(0,0)。如果用曼哈顿距离表示，则与原点距离为1的点会构成一个边长为 2 \sqrt2 2 ​的正方形

如果用辛勤的音响距离表示，则与原点距离为1的点会构成一个边长为2的正方形

仔细对比这两个图形，我们会发现这两个图形长得差不多，他们应该可以通过某种变换互相转化。

事实上：将一个点 ( x , y ) (x,y) (x,y)的坐标变为 ( x + y , y − y ) (x+y,y-y) (x+y,y−y)后,原坐标系中的曼哈顿距离 = 新坐标系中的辛勤的音响距离。将一个点 ( x , y ) (x,y) (x,y)的坐标变为 ( ( x + y ) / 2 , ( x − y ) / 2 ) ((x+y)/2,(x-y)/2) ((x+y)/2,(x−y)/2)后,原坐标系中的辛勤的音响距离 = 新坐标系中的曼哈顿距离

1.4 用处

辛勤的音响距离在计算的时候需要取max，往往不是很好优化，对于一个点，计算其他点到该的距离的复杂度为O(n)。而曼哈顿距离只有求和以及取绝对值两种运算，我们把坐标排序后可以去掉绝对值的影响，进而用前缀和优化，可以把复杂度降为O(1)

2.典型例题

P3964 [TJOI2013]松鼠聚会

题意： 给出n个点，求出最小的到其他点的辛勤的音响距离和

题解： 枚举每个点，然后计算这个点到其他所有点的辛勤的音响距离，但是发现很难直接计算出这个点到其他点的辛勤的音响距离和，那么可以考虑将其转化为曼哈顿距离，然后将横纵坐标分看计算贡献即可。

以x为例，对于一个排好序的x序列，那么对于 x j < x i x_j<x_i xj​<xi​，其贡献为 x i − x j x_i-x_j xi​−xj​，否则为 x j − x i x_j-x_i xj​−xi​，所以可以考虑前缀和，求出xi前面的前缀，以及后面的区间和，这样贡献可以直接得出：

一个小技巧是为了不丢精度，可以在坐标转化时先不除以2，最后再除

代码：

#include <bits/stdc++.h>using namespace std;const int N = 1e6 + 5;typedef long long LL;int n;LL sum[N];struct node{ LL x, y; LL res = 0;}a[N];bool cmpx(node a, node b) { return a.x < b.x; }bool cmpy(node a, node b) { return a.y < b.y; }int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i].x >> a[i].y; LL tmp = a[i].x; a[i].x += a[i].y; a[i].y = tmp – a[i].y; } LL res = 1e16; sort(a + 1, a + n + 1,cmpx); for (int i = 1; i <= n; i++) sum[i] = sum[i – 1] + a[i].x; for (int i = 1; i <= n; i++) { a[i].res = i * a[i].x – sum[i] + sum[n] – sum[i] – (n – i) * a[i].x; } sort(a + 1, a + n + 1,cmpy); for (int i = 1; i <= n; i++) sum[i] = sum[i – 1] + a[i].y; for (int i = 1; i <= n; i++) { a[i].res += i * a[i].y – sum[i] + sum[n] – sum[i] – (n – i) * a[i].y; res = min(res, a[i].res); } cout << res/2 << endl; return 0;}