GESP 2026年C++四级编程题解析

202603-1 山之谷#

题目描述

现有一片山地，可以视为一个 $N$ 行 $M$ 列的网格图，第 $i$ 行 $j$ 列的海拔为 $h_{i,j}$ 。

如果一个单元格的海拔不高于其所有相邻单元格（相邻包括上、下、左、右、左上、右上、左下、右下，最多 $8$ 个方向）的海拔，则称该单元格为山谷。

请你数一数该片山地中有多少山谷。

输入格式

第一行包含 $2$ 个整数 $N, M$ ，表示山地的大小。

之后 $N$ 行，每行包含 $M$ 个整数 $h_{i,1}, h_{i,2}, \cdots, h_{i,M}$ ，表示海拔。

输出格式

输出 $1$ 行，包含 $1$ 个整数 $C$ ，表示山谷的数量。

样例输入 1

样例输出 1

提示

【样例解释】

样例 1 如图所示，绿色单元格代表山谷：

【数据范围】

保证 $1 \leq N, M \leq 100$ ， $1 \leq h_{i,j} \leq 10^5$ 。

代码解析

这是一道经典的矩阵内枚举题目，我们可以枚举每个单元格，如果单元格周围的八个格子都大于单元格，则为山谷，答案加一。

为了避免枚举时越界，我们从 $(1,1)$ 开始枚举，到 $(n,m)$ 结束（越界则为 0），同时我们使用偏移数组 dx, dy 数组来表示八个方向，简化代码。

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n, m, cnt, a[105][105];
4

5
bool check(int i, int j) {
6
  int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
7
  int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
8
  for (int x = 0; x < 8; x++)
9
    for (int y = 0; y < 8; y++)
10
      if (a[i+dx[x]][j+dy[y]] < a[i][j] && a[i+dx[x]][j+dy[y]] != 0)
11
        return false;
12
  return true;
13
}
14

15
int main() {
16

17
  cin >> n >> m;
18
  for (int i = 1; i <= n; i++)
19
    for (int j = 1; j <= m; j++)
20
      cin >> a[i][j];
21
  for (int i = 1; i <= n; i++)
22
    for (int j = 1; j <= m; j++)
23
      if (check(i, j))
24
        cnt++;
25
  cout << cnt;
26

27
  return 0;
28
}

202603-2 礼盒排序#

题目描述

商店推出了许多礼盒，每个礼盒中包含 $k$ 件商品，每件商品都有一个价格。

现在需要对这些礼盒进行排序，排序规则如下：

先按礼盒总价格从小到大排序；
如果总价格相同，按礼盒中最贵商品的价格从小到大排序；
如果仍然相同，按礼盒中最便宜商品的价格从小到大排序；
如果仍然相同，按礼盒编号从小到大排序。

请输出排序后的礼盒编号。 输入格式

第一行包含两个整数 $n$ 和 $k$ ，分别表示礼盒数量和每个礼盒中商品的数量。

接下来 $n$ 行，每行包含 $k$ 个整数，第 $i$ 行表示第 $i$ 个礼盒中各商品的价格。

输出格式

输出一行，包含排序后的礼盒编号（编号从 $1$ 开始），用空格分隔。

样例输入 1

样例输出 1

3 4 2 1

提示

【样例解释】

编号	商品价格	总价	最大值	最小值
$1$	$3\ 5\ 2$	$10$	$5$	$2$
$2$	$4\ 1\ 5$	$10$	$5$	$1$
$3$	$2\ 2\ 4$	$8$	$4$	$2$
$4$	$3\ 4\ 3$	$10$	$4$	$3$

排序过程:

按总价排序， $3$ 号礼盒总价最小；
其余总价均为 $10$ ，再按最大值排序， $4$ 号最大值更小；
$1$ 号和 $2$ 号最大值相同，再按最小值排序， $2$ 号更小。

最终顺序为： $3 \ 4 \ 2 \ 1$

【数据范围】

保证 $1 \leq n \leq 10^3$ ， $1 \leq k \leq 10$ ， $1 \leq$ 商品价格 $\leq 10^4$ 。

代码解析

也是一道经典的四级常考结构体排序题目，但是注意不要陷入题目误区而去存储礼盒中所有商品的价格，对于每一个礼盒，我们只需要记录礼盒编号、礼盒总价格、礼盒中最贵商品价格、礼盒中最便宜商品价格即可。

1
#include<bits/stdc++.h>
2
using namespace std;
3
struct box {
4
  int idx, total = 0;
5
  int mi = 10005, ma = 0;
6
};
7
bool cmp(box a, box b) {
8
  if (a.total != b.total)
9
    return a.total < b.total;
10
  else if (a.ma != b. ma)
11
    return a.ma < b.ma;
12
  else if (a.mi != b.mi)
13
    return a.mi < b.mi;
14
  else
15
    return a.idx < b.idx;
16
}
17
int main() {
18

19
  int n, k, p;
20
  box a[1005];
21
  cin >> n >> k;
22
  for (int i = 0; i < n; i++) {
23
    for (int j = 0; j < k; j++) {
24
      cin >> p; // 输入商品价格时，更新礼盒总价格、最大值、最小值
25
      a[i].idx = i+1;
26
      a[i].total += p;
27
      a[i].mi = min(a[i].mi, p);
28
      a[i].ma = max(a[i].ma, p);
29
    }
30
  }
31
  sort(a, a+n, cmp);
32
  for (int i = 0; i < n; i++)
33
    cout << a[i].idx << ' ';
34

35
  return 0;
36
}