题解：P16293 [蓝桥杯 2026 省 Java A 组] 奇怪的地图
yz19
·
·
题解
P16293 [蓝桥杯 2026 省 Java A] 奇怪的地图 题解
题目大意
求最远的两座城市之间的距离。
### 公式解法
这题是有公式的，好多题解都是只写公式，我认为有必要把纯纯的推导过程写出来（有的人没背过公式）。
在六边形网格中，两点之间的距离是 $ \max\Bigl( |x_1 - x_2|,\ |y_1 - y_2|,\ \bigl|(x_1 - y_1) - (x_2 - y_2)\bigr| \Bigr)$。
### 单纯推导解法
这题看起来毫无头绪，但是我们可以把最远的两座城市之间的距离分解一下。
先举个例子吧，现在你要求班上最大的身高差距，你是不是会先找最高的，再找最矮的，最后一减，就出来了。
**这里有个数学知识：在六边形网格中，通常会再加一个维度 $z = x - y$。**
所以，最远的两座城市之间的距离其实就是每个维度（有三个维度）的最大值减最小值，最后再求这三个值的最大值。
不懂的可以看下面详细步骤：
1. 求出 $x$ 维度（坐标）的最大值减最小值
2. 求出 $y$ 维度（坐标）的最大值减最小值
3. 求出 $z = x - y$ 维度（坐标）的最大值减最小值
4. 求出这三个值的最大值
### 代码如下（Java）
```java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
long maxA = Long.MIN_VALUE, minA = Long.MAX_VALUE;
long maxB = Long.MIN_VALUE, minB = Long.MAX_VALUE;
long maxC = Long.MIN_VALUE, minC = Long.MAX_VALUE;
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
long x = Long.parseLong(st.nextToken());
long y = Long.parseLong(st.nextToken());
long a = x;
long b = y;
long c = x - y;
if (a > maxA) maxA = a;
if (a < minA) minA = a;
if (b > maxB) maxB = b;
if (b < minB) minB = b;
if (c > maxC) maxC = c;
if (c < minC) minC = c;
}
long ans = Math.max(maxA - minA,
Math.max(maxB - minB, maxC - minC));
System.out.println(ans);
}
}
```
时间复杂度 $O(n)$，空间复杂度 $O(1)$。
点个赞吧 QAQ，求求了！！