GESP C++
4级
真题
202512-建造(luogu-b4451)

202512-建造(luogu-b4451)

GESP C++ 2025年12月，四级真题第一题，考察二维数组遍历与简单的统计逻辑。题目难度⭐⭐☆☆☆。洛谷难度等级普及−。

第一题，建造(luogu-b4451)

题目要求

题目描述

小 A 有一张 MM 行 NN 列的地形图，其中第 ii 行第 jj 列的数字 aija_{ij} 代表坐标 (i,j)(i, j) 的海拔高度。

停机坪为一个 3×33 \times 3 的区域，且内部所有 99 个点的最大高度和最小高度之差不超过 HH。

小 A 想请你计算出，在所有适合建造停机坪的区域中，区域内部 99 个点海拔之和最大是多少。

输入格式

第一行三个正整数 M,N,HM, N, H，含义如题面所示。

之后 MM 行，第 ii 行包含 NN 个整数 ai1,ai2,…,aiNa_{i1}, a_{i2}, \dots, a_{iN}，代表坐标 (i,j)(i, j) 的高度。

数据保证总存在一个适合建造停机坪的区域。

输出格式

输出一行，代表最大的海拔之和。

输入输出样例 #1

输入 #1 
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 
40

说明/提示

数据范围

对于所有测试点，保证 1≤M,N≤1031 \leq M, N \leq 10^3，1≤H,aij≤1051 \leq H, a_{ij} \leq 10^5。

题目分析

1. 核心逻辑

题目要求在一个 M×NM \times N 的矩阵中，找到一个 3×33 \times 3 的子区域（停机坪），满足以下两个条件：

  1. 该 3×33 \times 3 区域内的极差（最大值减最小值）不超过 HH。
  2. 在满足上述条件的前提下，区域内 99 个元素的高度之和最大。

我们需要输出这个最大的和。

这是一个典型的二维数组遍历与局部统计的问题。由于 3×33 \times 3 的区域非常小（固定 9 个点），且 M,NM, N 的范围最大为 10001000，我们可以直接使用暴力枚举的方法。

2. 解题思路

  1. 遍历所有可能的停机坪：

一个 3×33 \times 3 的停机坪由其左上角的位置确定。假设左上角坐标为 (i,j)(i, j)，那么该 3×33 \times 3 区域的行范围是 [i,i+2][i, i+2]，列范围是 [j,j+2][j, j+2]。

要保证区域不越界，左上角的行坐标 ii 可以从 00 遍历到 M−3M-3，列坐标 jj 可以从 00 遍历到 N−3N-3。

  1. 检查每个区域是否合法：

对于每一个确定的 (i,j)(i, j)，我们需要遍历其对应的 3×33 \times 3 小矩阵内的 9 个元素：

  • 找出这 9 个数中的最大值和最小值。
  • 求出这 9 个数的和。

检查 最大值 - 最小值 是否 ≤H\le H。

  1. 更新答案：

如果当前区域合法（极差 ≤H\le H），则用当前区域的和去更新全局的最大和（max_sum）。

由于题目保证“总存在一个适合建造停机坪的区域”，我们初始化 max_sum 为一个较小值即可，或者在找到第一个合法区域时初始化。

3. 复杂度分析

  • 时间复杂度：

我们需要遍历 (M−2)×(N−2)(M-2) \times (N-2) 个可能的起始点。

对于每个起始点，我们需要遍历 3×3=93 \times 3 = 9 个元素。

总运算次数约为 9×M×N9 \times M \times N。

当 M,N=1000M, N = 1000 时，总次数约为 9×1069 \times 10^6，远小于一般的时间限制（通常为 10810^8 次运算/秒），因此暴力枚举完全可行。

  • 空间复杂度：

我们需要存储 M×NM \times N 的地图，空间复杂度为 O(M×N)O(M \times N)。

示例代码 

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

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于
202509-最长连续段(luogu-B4416)202512-优先购买