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

3 5
7 6 6 7 9
6 5 6 7 6
6 5 7 8 9

样例输出 1

3

提示

【样例解释】

样例 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$ 件商品，每件商品都有一个价格。

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

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

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

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

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

输出格式

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

样例输入 1

4 3
3 5 2
4 1 5
2 2 4
3 4 3

样例输出 1

3 4 2 1

提示

【样例解释】

排序过程:

1. 按总价排序，$3$ 号礼盒总价最小；
2. 其余总价均为 $10$，再按最大值排序，$4$ 号最大值更小；
3. $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
}

202606-1 扫雷#

题目描述

小杨同学正在游玩经典游戏「扫雷」，他想自己生成一个「扫雷」的地图。

小杨同学希望生成的地图大小为 $n$ 行 $m$ 列，一共 $n \times m$ 个区块。区块行号为 $1, 2, \cdots, n$，列号为 $1, 2, \cdots, m$。其中一些区块为雷区，其它区块不为雷区。

小杨同学指定了 $q$ 个区块为雷区，而其它区块均不为雷区。小杨同学希望你帮忙计算非雷区的区块，每个区块与多少个雷区相邻？

我们定义区块相邻，当且仅当两个区块至少有一个公共顶点（也就是说对于不在地图边缘的区块，周围 $8$ 个区块均与其相邻）。

输入格式

输入包含 $q + 1$ 行。

第一行，三个正整数 $n$, $m$ 和 $q$，分别表示地图行数和列数，以及雷区数量。

接下来的 $q$ 行，每行有 $2$ 个整数，分别表示第 $i$ 个雷区的行号和列号。

保证输入的雷区不重复。

输出格式

输出 $n$ 行，每行 $m$ 个字符（使用空格分割），对于第 $i$ 行第 $j$ 列，输出地图对应区块的信息：

1. 如果为雷区，输出 *；
2. 如果不是雷区，输出其相邻雷区数量（输出 $0$ 到 $8$ 中的一个数字）。

样例输入 1

3 4 4
1 1
1 3
2 4
3 2

样例输出 1

* 2 * 2
2 3 3 *
1 * 2 1

提示

【输出解释 1】

根据输入，在 $3 \times 4$ 的地图上有 $4$ 个雷区，分别是 $(1,1)$，$(1,3)$，$(2,4)$ 和 $(3,2)$，如输出样例中 * 所示，其它非雷区区块的相邻雷区数量可以直观看出。

【数据范围】

$3 \le n, m \le 500$, $1 \le q \le n \cdot m$。

输入的雷区必定在地图内且不重复，注意行号和列号均从 $1$ 开始。

代码解析

这道题比较简单，我们定义一个 bool 数组 $a$ ，$a[i][j]$ 表示第 $i$ 行第 $j$ 列是否为雷。再用一个 int 数组 $b$ 来表示地图中每个格子周围相邻格子中雷的数量。

在输入数据的同时我们使用偏移数组 $dx$ 和 $dy$ 来遍历周围的 8 个方向，更新周围相邻格子中雷的数量即可，不需要输入结束后再去重新统计。

1
#include <bits/stdc++.h>
2
using namespace std;
3
int main() {
4

5
    bool a[1005][1005] = {0};
6
    int b[1005][1005] = {0};
7
    int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
8
    int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
9
    int n, m, p;
10
    cin >> n >> m >> p;
11
    while (p--) {
12
        int r, c;
13
        cin >> r >> c;
14
        a[r][c] = 1;
15
        for (int i = 0; i < 8; i++)
16
            b[r+dx[i]][c+dy[i]]++;
17
    }
18

19
    for (int i = 1; i <= n; i++) {
20
        for (int j = 1; j <= m; j++)
21
            if (a[i][j]) cout << "* ";
22
            else cout << b[i][j] << ' ';
23
        cout << endl;
24
    }
25

26
    return 0;
27
}

202606-2 身高体重指数#

题目描述

一个人的身高体重指数（BMI）等于其体重（千克为单位）除以其身高（米为单位）的平方。

例如，一个体重为 $50\text{ kg}$，身高为 $1.6\text{ m}$ 的人的身高体重指数为 $50\text{ kg}/1.6\text{ m}/1.6\text{ m} = 19.53125\text{ kg/m}^2$。

现在有 $n$ 个小朋友，第 $i$ 个小朋友的编号为 $i$，体重为 $w_i$，身高为 $h_i$。

请按照身高体重指数从高到低为小朋友们排序，数据保证不存在两个小朋友的身高体重指数完全相同。输出排序后小朋友的编号。

输入格式

输入 $3$ 行，

第一行为一个正整数 $n$，表示小朋友的个数；

第二行为 $n$ 个整数 $w_1, w_2, \cdots, w_n$ 表示小朋友们的体重，单位为 $\text{kg}$；

第三行为 $n$ 个浮点数 $h_1, h_2, \cdots, h_n$ 表示小朋友们的身高，单位为 $\text{m}$。

输出格式

输出一行 $n$ 个数，表示按照身高体重指数从高到低排序后的编号。

样例输入 1

3
45 33 39
1.55 1.33 1.44

样例输出 1

3 1 2

提示

【样例解释】

三个小朋友（编号依次为 $1$，$2$，$3$）的身高体重指数分别为（保留两位小数的结果）：$18.73$，$18.66$，$18.81$，故排序后输出的编号为 $3\ 1\ 2$。

【数据范围】

$1 \le n \le 1000$，$10 \le w_i \le 100$，$0.8 \le h_i \le 1.9$，$h_i$ 均恰有两位小数。

代码解析

这是一道结构体数组的基础题，根据题意，需要对结构体数组按照 bmi 排序之后，输出排序后的编号，所以我们在结构体中添加一个成员变量 idx 来表示原始的编号，在输入数据的过程中完成初始化，最后排序输出即可，注意编号从 $1$ 开始。

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
struct stu {
5
    double w, h, bmi;
6
    int idx;
7
} a[1005];
8

9
bool cmp(stu a, stu b) {
10
    return a.bmi > b.bmi;
11
}
12

13
int main() {
14

15
    int n;
16
    cin >> n;
17
    for (int i = 1; i <= n; i++) {
18
        cin >> a[i].w;
19
        a[i].idx = i;
20
    }
21
    for (int i = 1; i <= n; i++) {
22
        cin >> a[i].h;
23
        a[i].bmi = a[i].w / (a[i].h * a[i].h);
24
    }
25

26
    sort(a+1, a+n+1, cmp);
27
    for (int i = 1; i <= n; i++)
28
        cout << a[i].idx << ' ';
29

30
    return 0;
31
}