【GESP】C++ 四级真题解析，[2025年12月，第十二次认证]第一题建造 luogu-b4451
GESP C++ 2025年12月，四级真题第一题，考察二维数组遍历与简单的统计逻辑。题目难度⭐⭐☆☆☆。
第一题，建造(luogu-b4451)
题目要求
题目描述
小 A 有一张 $M$ 行 $N$ 列的地形图，其中第 $i$ 行第 $j$ 列的数字 $a_{ij}$ 代表坐标 $(i, j)$ 的海拔高度。
停机坪为一个 $3 \times 3$ 的区域，且内部所有 $9$ 个点的最大高度和最小高度之差不超过 $H$。
小 A 想请你计算出，在所有适合建造停机坪的区域中，区域内部 $9$ 个点海拔之和最大是多少。
输入格式
第一行三个正整数 $M, N, H$，含义如题面所示。
之后 $M$ 行，第 $i$ 行包含 $N$ 个整数 $a_{i1}, a_{i2}, \dots, a_{iN}$，代表坐标 $(i, j)$ 的高度。
数据保证总存在一个适合建造停机坪的区域。
输出格式
输出一行，代表最大的海拔之和。
输入输出样例 #1
输入 #1
1
2
3
4
5
6
5 5 3
5 5 5 5 5
5 1 5 1 5
5 5 5 5 5
5 2 5 2 5
3 5 5 5 2
输出 #1
1
40
说明/提示
数据范围
对于所有测试点，保证 $1 \leq M, N \leq 10^3$，$1 \leq H, a_{ij} \leq 10^5$。
题目分析
1. 核心逻辑
题目要求在一个 $M \times N$ 的矩阵中，找到一个 $3 \times 3$ 的子区域（停机坪），满足以下两个条件：
- 该 $3 \times 3$ 区域内的极差（最大值减最小值）不超过 $H$。
- 在满足上述条件的前提下，区域内 $9$ 个元素的高度之和最大。
我们需要输出这个最大的和。
这是一个典型的二维数组遍历与局部统计的问题。由于 $3 \times 3$ 的区域非常小（固定 9 个点），且 $M, N$ 的范围最大为 $1000$，我们可以直接使用暴力枚举的方法。
2. 解题思路
- 遍历所有可能的停机坪：
一个 $3 \times 3$ 的停机坪由其左上角的位置确定。假设左上角坐标为 $(i, j)$，那么该 $3 \times 3$ 区域的行范围是 $[i, i+2]$，列范围是 $[j, j+2]$。
要保证区域不越界，左上角的行坐标 $i$ 可以从 $0$ 遍历到 $M-3$，列坐标 $j$ 可以从 $0$ 遍历到 $N-3$。
- 检查每个区域是否合法：
对于每一个确定的 $(i, j)$，我们需要遍历其对应的 $3 \times 3$ 小矩阵内的 9 个元素：
- 找出这 9 个数中的最大值和最小值。
- 求出这 9 个数的和。
检查 最大值 - 最小值 是否 $\le H$。
- 更新答案：
如果当前区域合法（极差 $\le H$），则用当前区域的和去更新全局的最大和（max_sum）。
由于题目保证“总存在一个适合建造停机坪的区域”，我们初始化 max_sum 为一个较小值即可，或者在找到第一个合法区域时初始化。
3. 复杂度分析
- 时间复杂度：
我们需要遍历 $(M-2) \times (N-2)$ 个可能的起始点。
对于每个起始点，我们需要遍历 $3 \times 3 = 9$ 个元素。
总运算次数约为 $9 \times M \times N$。
当 $M, N = 1000$ 时，总次数约为 $9 \times 10^6$，远小于一般的时间限制（通常为 $10^8$ 次运算/秒），因此暴力枚举完全可行。
- 空间复杂度：
我们需要存储 $M \times N$ 的地图，空间复杂度为 $O(M \times N)$。
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <climits>
#include <cmath>
#include <iostream>
// 定义最大数组大小，根据题目要求 M, N <= 1000
int a[1005][1005];
int main() {
int M, N, H;
// 输入行数 M，列数 N，和最大高度差限制 H
std::cin >> M >> N >> H;
// 读取地图高度数据
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
std::cin >> a[i][j];
}
}
int max_sum = INT_MIN; // 用于记录满足条件区域的最大海拔之和
// 遍历每一个可能的 3x3 区域的左上角起点 (i, j)
// 因为停机坪是 3x3 的区域，所以 i 的范围是 0 到 M-3，j 的范围是 0 到 N-3
for (int i = 0; i <= M - 3; i++) {
for (int j = 0; j <= N - 3; j++) {
int tmp_sum = 0;
int tmp_max = INT_MIN;
int tmp_min = INT_MAX;
// 遍历 3x3 区域内的每一个点 (k, l)
// k 从 i 到 i+2，l 从 j 到 j+2
for (int k = i; k <= i + 2; k++) {
for (int l = j; l <= j + 2; l++) {
tmp_sum += a[k][l];
// 更新区域内的最大值和最小值
tmp_max = std::max(tmp_max, a[k][l]);
tmp_min = std::min(tmp_min, a[k][l]);
}
}
// 判断最大高度差是否满足条件：max - min <= H
if (tmp_max - tmp_min > H) {
continue;
}
// 如果满足条件，更新全局最大和
max_sum = std::max(max_sum, tmp_sum);
}
}
std::cout << max_sum << '\n';
return 0;
}
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
