ABC437B 抽奖游戏
ABC437B 抽奖游戏
【算法标签】 数据结构/数组/下标映射
【语法标签】 :数组、for循环、下标映射
有一个 行 列的网格(,),每个格子中写有一个互不相同的整数 。
主持人喊出 个互不相同的整数 ()。
对于每一行,统计主持人喊出的整数中有多少个出现在该行中。求这些计数的最大值。
所有整数都在 之间。
二、解题思路
2.1 数据规模分析
| 参数 | 范围 | 含义 |
|---|---|---|
| 行数,非常小 | ||
| 列数,非常小 | ||
| 主持人喊的数字个数 | ||
| , | 所有数字范围很小 |
数据量极小,甚至暴力 也能过。但我们可以做得更优雅。
2.2 核心思路:反向映射
题目问的是:每个 出现在哪一行?
如果我们拿着每个 去网格里找,每次都要扫描整个网格(),总共 。虽然数据小也能过,但不够漂亮。
更好的做法——因为 互不相同且值域只有 ,我们可以建一个反向映射:
rowOf[值] = 该值所在的行号
这样对于每个 ,查 rowOf[B[i]] 就知道它在第几行,然后给那一行的计数器 +1。时间复杂度 。
2.3 手动模拟样例
样例 1:
网格:
第1行: 12 3 5 7
第2行: 6 10 11 9
第3行: 1 2 4 8建立映射:
rowOf[12]=1, rowOf[3]=1, rowOf[5]=1, rowOf[7]=1
rowOf[6]=2, rowOf[10]=2, rowOf[11]=2, rowOf[9]=2
rowOf[1]=3, rowOf[2]=3, rowOf[4]=3, rowOf[8]=3主持人喊:2, 4, 9, 6, 11
| 所在行 | 操作 | |
|---|---|---|
| 2 | 第 3 行 | cnt[3] = 1 |
| 4 | 第 3 行 | cnt[3] = 2 |
| 9 | 第 2 行 | cnt[2] = 1 |
| 6 | 第 2 行 | cnt[2] = 2 |
| 11 | 第 2 行 | cnt[2] = 3 |
最终 cnt = [0, 0, 3, 2],最大值 = 3。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int M = 91; // 数字最大 90
int rowOf[M]; // rowOf[x] = 数字 x 所在的行号(1~H)
int cnt[M]; // cnt[r] = 第 r 行中被喊到的数字个数
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int h, w, n;
cin >> h >> w >> n;
// 读入网格,建立反向映射
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++) {
int x;
cin >> x;
rowOf[x] = i; // 数字 x 在第 i 行
}
}
// 处理主持人喊的数字
for (int i = 1; i <= n; i++) {
int b;
cin >> b;
int r = rowOf[b]; // 这个数字在哪一行
cnt[r]++; // 该行计数 +1
}
// 取最大值
int ans = 0;
for (int r = 1; r <= h; r++) {
ans = max(ans, cnt[r]);
}
cout << ans << endl;
return 0;
}代码要点
| 写法 | 说明 |
|---|---|
rowOf[x] = i | 记录数字 出现在第 行(反向映射) |
cnt[r]++ | 第 行命中计数 +1 |
const int M = 91 | 数组开到 91(比最大数字 90 大 1),下标直接对应数字值 |
max(ans, cnt[r]) | 遍历每行取最大值 |
下标映射 vs 直接扫描
直接扫描(每个 B 都去网格里找):
for (int i = 1; i <= n; i++) {
int b;
cin >> b;
for (int r = 1; r <= h; r++)
for (int c = 1; c <= w; c++)
if (a[r][c] == b)
cnt[r]++; // 找到了
}时间复杂度 ,最坏约 次操作,也能过。
反向映射(本题做法):
时间复杂度 ,且代码更清晰。当值域小、数字互异时,这是一个常用技巧。
四、复杂度分析
| 项目 | 复杂度 | 说明 |
|---|---|---|
| 时间 | 建映射 + 处理 N 个查询,每次 O(1) | |
| 空间 | 两个大小为 91 的数组,常数级 |
数据量极小,无论哪种写法都能轻松通过。
五、知识扩展
下标映射(反向索引)
当我们频繁需要"查某个值在哪个位置"时,如果值域不大,可以反过来存——以值为下标,以位置为数组元素。
正向存储(原数据):
grid[行][列] = 值 → 查位置慢:需要扫描
反向映射:
rowOf[值] = 行号 → 查位置快:直接 O(1)常见应用场景:
- 题目给了互不相同的编号,要求按编号查位置
- 值域较小(如本题的 1~90,或 ASCII 码的 0~255)
- 需要多次快速查询
另一个经典例子——字符串中找字符位置:
int pos[256]; // 字符 ASCII 码 → 位置
for (int i = 0; i < s.size(); i++)
pos[s[i]] = i; // 记录每个字符最后出现的位置六、易错点
数组开太小:如果开
rowOf[90],下标最大只能用 89,数字 90 会越界。保险写法:const int M = 最大值 + 1,即M = 91。计数数组要清零:全局数组(定义在
main外面)自动初始化为 0,如果写在main里面记得手动清零或用{}初始化。不要混淆行列编号:题目中行号从 1 开始,列号从 1 开始,和代码保持一致。
