: 建造)
2025年12月GESP(C++四级): 建造
题目描述
小 A 有一张M MM行N NN列的地形图，其中第i ii行第j jj列的数字a i j a_{ij}aij代表坐标( i , j ) (i, j)(i,j)的海拔高度。
停机坪为一个3 × 3 3 \times 33×3的区域，且内部所有9 99个点的最大高度和最小高度之差不超过H HH。
小 A 想请你计算出，在所有适合建造停机坪的区域中，区域内部9 99个点海拔之和最大是多少。
输入格式
第一行三个正整数M , N , H M, N, HM,N,H，含义如题面所示。
之后M MM行，第i ii行包含N NN个整数a i 1 , a i 2 , … , a i N a_{i1}, a_{i2}, \dots, a_{iN}ai1,ai2,…,aiN，代表坐标( i , j ) (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 ≤ 10 3 1 \leq M, N \leq 10^31≤M,N≤103，1 ≤ H , a i j ≤ 10 5 1 \leq H, a_{ij} \leq 10^51≤H,aij≤105。
思路分析
这个问题要求在 M×N 的地形图中，找到一个 3×3 的区域，满足区域内9个点中最大高度和最小高度之差不超过 H，并且在所有满足条件的区域中找到海拔之和最大的区域。
核心思想
- 暴力枚举法：遍历所有可能的 3×3 区域的左上角坐标
- 边界条件：由于是 3×3 区域，左上角坐标范围为
(1 ≤ i ≤ m-2, 1 ≤ j ≤ n-2) - 条件检查：对每个区域，计算最大值和最小值，检查差值是否 ≤ H
- 求和计算：对符合条件的区域计算9个点的和，并更新最大值
时间复杂度
- 外层循环：O((M-2)×(N-2)) ≈ O(M×N)
- 内层循环：固定 9 次操作（3×3 区域）
- 总复杂度：O(M×N)，在 M,N ≤ 1000 时是可行的
代码实现
#include<bits/stdc++.h>usingnamespacestd;intm,n,h,ans=0,a[1010][1010];// 检查以(x,y)为左上角的3×3区域是否满足高度差条件boolcheck(intx,inty){intmaxh=a[x][y];// 最大值初始化为第一个元素intminh=a[x][y];// 最小值初始化为第一个元素// 遍历3×3区域的所有9个点for(inti=x;i<=x+2;i++){for(intj=y;j<=y+2;j++){maxh=max(maxh,a[i][j]);// 更新最大值minh=min(minh,a[i][j]);// 更新最小值}}// 判断最大高度差是否不超过Hreturnmaxh-minh<=h;}// 计算以(x,y)为左上角的3×3区域的海拔之和intsum(intx,inty){intres=0;// 遍历3×3区域的所有9个点并累加for(inti=x;i<=x+2;i++){for(intj=y;j<=y+2;j++){res+=a[i][j];}}returnres;}intmain(){// 输入数据规模cin>>m>>n>>h;// 输入地形图数据for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){cin>>a[i][j];}}// 枚举所有可能的3×3区域的左上角// i的范围：1 到 m-2（保证向下有3行）// j的范围：1 到 n-2（保证向右有3列）for(inti=1;i<=m-2;i++){for(intj=1;j<=n-2;j++){// 如果当前区域满足高度差条件if(check(i,j)){// 计算区域和并更新最大值ans=max(ans,sum(i,j));}}}// 输出最大海拔和cout<<ans;return0;}功能分析
1.数据结构
- 使用二维数组
a[1010][1010]存储地形图 - 数组大小定义为 1010×1010，满足 M,N ≤ 1000 的要求
2.核心函数
check(x, y)：检查指定区域是否满足建造条件- 时间复杂度：O(9) = O(1)
- 空间复杂度：O(1)
sum(x, y)：计算指定区域的海拔总和- 时间复杂度：O(9) = O(1)
- 空间复杂度：O(1)
3.算法流程
1. 读取输入：M, N, H 和地形图数据 2. 遍历所有可能的3×3区域左上角坐标 - 对每个区域调用check()检查是否满足条件 - 如果满足，调用sum()计算海拔和并更新最大值 3. 输出找到的最大海拔和4.边界处理
- 循环条件
i <= m-2和j <= n-2确保3×3区域不越界 - 题目保证至少存在一个满足条件的区域，所以ans一定有值
5.复杂度分析
- 时间复杂度：O(M×N × 9) ≈ O(9MN) = O(MN)
- 空间复杂度：O(MN) 用于存储地形图
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}- 一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
- 二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
- 三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解
详细内容：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
3、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
- 2025 csp-j 复赛真题及答案解析（最新更新）
- 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
- 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
- 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
- 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
- 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
- 2020 ~ 2024 csp 复赛真题题单及题解
- 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
- 2021 ~ 2024 csp-s 初赛高频考点解析
- 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
- 2024 csp-j 初赛真题及答案解析
- 2025 csp-j 初赛真题及答案解析（最新更新）
- 2025 csp-s 初赛真题及答案解析（最新更新）
- 2025 csp-x (山东)初赛真题及答案解析(最新更新)
- 2025 csp-x (江西)初赛真题及答案解析(最新更新)
- 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
- 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图
4、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
