编程题
B4451 建造
【题目来源】
洛谷：[B4451 GESP202512 四级] 建造 - 洛谷
【题目描述】
小 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)\) 的高度。
数据保证总存在一个适合建造停机坪的区域。
【输出】
输出一行，代表最大的海拔之和。
【输入样例】
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
【输出样例】
40
【算法标签】
《洛谷 B4451 建造》 #枚举# #GESP# #2025#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1005; // 定义最大矩阵大小
int n, m, h; // n: 行数, m: 列数, h: 高度差阈值
int ans = -1e9; // 初始化答案为负无穷
int a[N][N]; // 存储输入矩阵int main()
{// 输入矩阵的行数n、列数m和高度差阈值hcin >> n >> m >> h;// 输入n×m的矩阵for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){cin >> a[i][j];}}// 遍历所有可能的3×3子矩阵// 注意：循环条件是i<n+3而不是i<=n，存在越界访问的bugfor (int i = 1; i < n + 3; i++) // 行起始位置{for (int j = 1; j < m + 3; j++) // 列起始位置{// 当前3×3子矩阵的最小值和最大值int minn = a[i][j];int maxn = a[i][j];int res = 0; // 当前3×3子矩阵的元素和// 遍历当前3×3子矩阵for (int x = i; x < i + 3; x++){for (int y = j; y < j + 3; y++){// 累加元素值res += a[x][y];// 更新最小值和最大值minn = min(minn, a[x][y]);maxn = max(maxn, a[x][y]);}}// 判断当前3×3子矩阵的最大高度差是否小于等于hif (maxn - minn <= h){// 更新满足条件的最大元素和ans = max(ans, res);}}}// 输出结果cout << ans << endl;return 0;
}
【运行结果】
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
40
B4452 优先购买
【题目来源】
洛谷：[B4452 GESP202512 四级] 优先购买 - 洛谷
【题目描述】
小 A 有 \(M\) 元预算。商店有 \(N\) 个商品，每个商品有商品名 \(S\)、价格 \(P\) 和优先级 \(V\) 三种属性，其中 \(V\) 为正整数，且 \(V\) 越小代表商品的优先级越高。
小 A 的购物策略为：
- 总是优先买优先级最高的东西；
- 如果有多个最高优先级商品，购买价格最低的；
- 如果有多个优先级最高且价格最低的商品，购买商品名字典序最小的。
小 A 想知道能购买哪些商品。
【输入】
第一行两个正整数 \(M, N\)，代表预算和商品数。
之后 \(N\) 行，每行一个商品，依次为 \(S_i\ P_i\ V_i\)，代表第 \(i\) 个商品的商品名、价格、优先级。
数据保证不存在两个名字相同的商品。
【输出】
按照字典序从小到大的顺序，输出所有购买商品的商品名。
【输入样例】
20 4
apple 6 8
bus 15 1
cab 1 10
water 4 8
【输出样例】
bus
cab
water
【算法标签】
《洛谷 B4452 优先购买》 #排序# #GESP# #2025#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1005; // 最大物品数量// 定义物品结构体
struct Node
{string s; // 物品名称int p; // 物品价格int v; // 物品评分/价值
};Node a[N]; // 存储所有物品
Node b[N]; // 存储购买的物品
int m, n; // m: 预算, n: 物品总数
int cur; // 已购买物品数量// 第一个比较函数：用于初始排序
// 排序优先级：v(评分)升序 → p(价格)升序 → s(名称)字典序
bool cmp(Node x, Node y)
{if (x.v != y.v) return x.v < y.v; // 先按评分升序排序if (x.p != y.p) return x.p < y.p; // 评分相同，按价格升序return x.s < y.s; // 评分和价格都相同，按名称字典序
}// 第二个比较函数：按名称字典序排序
bool cmp2(Node x, Node y)
{return x.s < y.s; // 只按名称字典序排序
}int main()
{// 输入预算m和物品数量ncin >> m >> n;// 输入n个物品的信息for (int i = 1; i <= n; i++){cin >> a[i].s >> a[i].p >> a[i].v;}// 步骤1：对物品进行排序// 排序规则：先按v升序，v相同按p升序，都相同按s字典序sort(a + 1, a + n + 1, cmp);// 步骤2：在预算范围内尽可能多地购买物品for (int i = 1; i <= n; i++){// 如果当前预算足够购买第i个物品if (m >= a[i].p){m -= a[i].p; // 扣除价格b[++cur] = a[i]; // 将物品加入购买列表}// 这里不能break，因为后面可能有更便宜的物理可购买}// 步骤3：对购买的物品按名称字典序排序sort(b + 1, b + cur + 1, cmp2);// 步骤4：输出购买的物品名称for (int i = 1; i <= cur; i++){cout << b[i].s << endl;}return 0;
}
【运行结果】
20 4
apple 6 8
bus 15 1
cab 1 10
water 4 8
bus
cab
water