L1-005考试座位号：从数组下标到哈希映射的入门题

有人看到"L1-005 考试座位号 -15分"这个标题，第一反应多半是：这不就是个查表题？15分的送分题能写出什么花来？

说实话，我第一次在PTA题库里刷到这道题时也是这么想的。但真正耐下心把题目读透、把代码跑通、把边界条件想清楚之后，我发现这道题其实非常能检验一个人对"数据该怎么组织"的判断力。尤其对于刚接触算法竞赛、刚学完结构体或者字典的小朋友来说，这道题既是一道温暖的入门题，又是一面能照出后续编码习惯的镜子。

这篇文章我就拿它当例子，把从读题到AC的完整过程拆开来讲。不光给代码，还会讲清楚每步为什么这么做、踩过哪些坑、考场上应该用什么节奏去做。适合刚学编程不久、准备打团体程序设计天梯赛，或者单纯想提升C语言和Python基本功的读者。整个过程大概需要你静下心跟我一起推演二十分钟，收获绝对对得起这二十分钟。

1. 题目到底在问什么，先读懂数据流

1.1 题目背景与输入输出格式还原

题目名字叫"考试座位号"，单看名字很容易误以为要算座位号，其实不是。它的真实场景是：一场考试前，每个考生会拿到一个试机座位号，用于入场后先坐到临时位置；正式开考前，考生需要找到自己的考试座位号对应的正式座位。监考老师手里有一份名单，包含考生的准考证号、试机座位号和考试座位号。现在考生只知道自己的试机座位号，我们得帮忙输出这个人的准考证号和考试座位号。

输入格式是这样的：第一行给出一个正整数 N，表示考生总人数。接下来 N 行，每行按顺序给出一名考生的准考证号、试机座位号、考试座位号。再接下来一行给出正整数 M，表示待查询的考生数量。最后一行给出 M 个试机座位号，用空格隔开。输出要求是对每个待查询的试机座位号，输出对应考生的准考证号和考试座位号，中间用空格隔开，每个查询结果占一行。

N 和 M 通常都在 1000 以内，15 分的题不会给很大的数据范围。所以从纯复杂度角度看，这题根本不缺解法，哪怕是每次查询都把所有考生信息从头到尾扫一遍，也就是 O(N*M) 的量级，N、M 都是 1000 的话，一百万次操作，计算机眨眼就完成。

1.2 最容易犯的第一个错：把准考证号当数字存

很多第一次写这道题的人，看到"准考证号"四个字，再看看样例输出里那一串数字，下意识就定义成 long long 甚至直接 int 去存。这是一个非常典型的新手错误。

准考证号虽然长成数字的样子，但它本质上是字符串，是"标识符"而不是"数值"。考试场景里，准考证号经常带上考场代码、年份、科目代码等信息，如果直接当数字解析，后续如果要在前面补零、或者中间出现字母，程序就崩了。退一步说，就算这道题的测试数据里准考证号全部是纯数字，用整数类型存储也没有任何好处，反而会在输出格式上给自己挖坑。

正确的做法只有一种：把准考证号定义成字符数组或者 string。C语言里给它 20 个字节就很宽裕，Python 里直接用字符串天然承接。这一点想明白，后面的结构体设计就顺了。

2. 两种解题思路的对比，暴力遍历 vs 映射索引

2.1 暴力遍历能过，但我们应该有更高的追求

第一种方案很直接：把所有考生信息存进结构体数组，M 次查询，每次都遍历一遍整个数组，比较当前考生的试机座位号和查询目标是否相等，相等就输出。

这个方案错吗？不错。测试数据小的话它百分百能 AC。但我个人不太推荐一上来就选它，原因不是性能，而是它会浪费一次训练"抽象建模"的机会。算法题和业务代码不一样，业务代码讲究尽快跑通，算法题讲究把数据关系想透。试机座位号和考生信息之间是一对一的映射关系，这种关系是最典型的"键-值"结构，用遍历去做，等于明明有钥匙要去一间间试锁孔。

刻意训练的价值在于：养成先想数据结构、再写代码的习惯。哪怕数据规模小到用不用优化都无所谓，你在脑子过一遍映射方案再动手，写出来的代码普遍会更清爽，后面遇到的测试点也更难出错。

2.2 用试机座位号做数组下标，核心思路一句话讲透

考试场景里有一个关键信息：试机座位号是有限范围内的整数，而且从输入数据的设计习惯来看，它是相对集中的连续编号，范围通常不会比 N 大太多。既然座位号是整数，那就完全可以用它直接当数组下标。

新建一个长度为 1005（或者 N+5）的结构体数组 seat，读入第 i 个考生的信息时，不按顺序放进 seat[i]，而是把信息放到 seat[试机座位号] 的位置。查询时输入一个目标座位号 x，直接输出 seat[x] 里的准考证号和考试座位号。

这样把"查找"变成了"定位"，时间复杂度从 O(M*N) 直接降到 O(N+M)。15 分的题谈时间复杂度好像有点小题大做，但这种"用数组下标替代查找"的思路，放到后续很多题目里都是非常实用的技巧。它本质上就是哈希表的雏形：用下标直接计算出存储位置，一步到位。

3. C语言实现与逐行讲解

3.1 结构体怎么设计才合理

既然方案定了，C语言这边就是结构体 + 数组两件套。每个考生的信息包含三个字段：准考证号、试机座位号、考试座位号。其中试机座位号在存储时其实可以不当成员存，因为它已经作为下标被"编码"进数组位置里了，存不存都不影响输出结果。

但为了代码可读性和逻辑完整，通常我还是会把三个字段都放进结构体里，查询的时候只取前两个输出即可。定义成：

typedef struct { char id[20]; int testSeat; int examSeat; } Student;

这个结构体在内存里是很紧凑的，20 字节字符串加上两个 int，一共 28 字节左右（各家编译器对齐略有差异）。N 最大 1000，也就是约 28KB 内存，随便用，不用担心超显存内存。

如果后续真的遇到座位号范围很大的题目，比如座位号能到 1 亿，数组开不下，那时候再考虑用哈希表或者平衡树去替代。这是后话，这题用数组就够了。

3.2 完整代码与关键点注释

下面这份是我在PTA上实际提交过的版本，为了便于阅读，我在关键位置加了注释：

#include <stdio.h> typedef struct { char id[20]; // 准考证号 int testSeat; // 试机座位号 int examSeat; // 考试座位号 } Student; int main() { int n, m; scanf("%d", &n); Student students[1005] = {0}; // 用试机座位号直接索引 for (int i = 0; i < n; i++) { char id[20]; int testSeat, examSeat; scanf("%s %d %d", id, &testSeat, &examSeat); // 关键：把信息存到 "testSeat" 对应的下标位置 for (int j = 0; j < 20 && id[j] != '\0'; j++) { students[testSeat].id[j] = id[j]; } students[testSeat].testSeat = testSeat; students[testSeat].examSeat = examSeat; } scanf("%d", &m); for (int i = 0; i < m; i++) { int querySeat; scanf("%d", &querySeat); printf("%s %d\n", students[querySeat].id, students[querySeat].examSeat); } return 0; }

注意我这里的字符串复制用了循环手动拷贝，看起来有点啰嗦，但既然不想引入 string.h 的 strcpy，这样写也足够清晰和安全。实际提交时你完全可以直接strcpy(students[testSeat].id, id);，效果一样，代码更短。

核心逻辑只有两个动作：读入时按下标存，查询时按下标取。其余都是输入输出的格式活。很多人拿到这道题会想把所有信息读进一个数组再排序或二分，其实完全没必要，因为输入的顺序没有要求，座位号作为天然的键，直接把数组中的"位置"当作查找依据才是最省事的。

3.3 编译运行中三个容易出错的细节

第一，数组下标从 1 开始还是从 0 开始？题目里的试机座位号一般是 1 到 N 的正整数，所以数组开 1005 大小并把信息存到 [1] 到 [N] 的位置是合理的，[0] 空着不用，避免下标越界和"差一错误"。查询的座位号也在这个范围里，所以不会访问到未初始化的位置。

第二，scanf 的格式串别加多余空格。我知道有的同学喜欢在 %d 之间加空格让输入格式"更可读"，但 scanf 本身就会跳过空白字符，加不加行为一致，万一加错了反而容易踩坑。保持scanf("%d", &n)这种最朴素的用法最稳。

第三，准考证号用%s读入的时候不需要&，因为数组名本身就是地址。这里我再强调一次，因为每届都有新手在这里懵圈。写scanf("%s", id)是正确且标准的，写scanf("%s", &id)虽然很多编译器不报错，但会产生警告，严格评测环境下属于不规范代码。

4. Python实现思路与代码对比

4.1 用字典做映射，Python版本只要二十行

Python 这边实现起来更简单，最符合题意的数据结构是字典。试机座位号作为字典的 key，一个包含准考证号和考试座位号的小列表或元组作为 value。查询时直接用方括号取，代码像说话一样直白：

n = int(input()) students = {} for _ in range(n): line = input().split() student_id = line[0] test_seat = int(line[1]) exam_seat = int(line[2]) students[test_seat] = (student_id, exam_seat) m = int(input()) query_seats = list(map(int, input().split())) for seat in query_seats: student_id, exam_seat = students[seat] print(f"{student_id} {exam_seat}")

这个版本我拿样例测过，输入、输出格式完全贴合题目要求，直接提交能过。Python 的解包语法student_id, exam_seat = students[seat]很爽，一行搞定两个变量的赋值，比写info = students[seat]; print(info[0], info[1])要优雅不少。

在Python的解法里，映射关系被字典这个内置类型表达得淋漓尽致。试机座位号作为键，理论上不需要关心号码是否连续，因为字典本身用哈希表实现，任何整数都能作为键存进去。这比 C 语言里必须开连续数组要灵活，但本质思路完全一致：不遍历、直接定位。

4.2 两种语言解法摆在一起，性能差距有多大

C 语言版本的时间复杂度是 O(N+M)，空间是 O(N)。Python 版本因为使用了哈希表，理论上查询是平均 O(1)，整体也是 O(N+M)，空间同样是 O(N)。但常量上 C 会快很多，毕竟字典的哈希计算有额外开销。

现实中这道题 N、M 都是 1000 左右，C 代码跑起来是零点几毫秒级别，Python 也就是几毫秒级别，都不会超时。所以选哪种语言完全看你的主攻方向：打比赛用 C/C++ 的同学就老老实实练习结构体和数组下标；非科班想快速做题的用 Python 字典会写得飞快。

我个人建议：如果时间允许，这道题两种语言都写一遍。因为它的代码量足够小，适合作为"同题双写"的练习素材，专门训练把一种数据结构的思路从 C 翻译到 Python、或者反过来翻译的能力。这种翻译练习对编程思维的迁移非常有帮助。

5. 实测踩坑记录，这些细节不试不知道

5.1 我提交时遇到的两个真实问题

第一次写这道题时，我把准考证号定义成了 long long。样例数据很小，跑一遍完全没毛病，提交也是直接 AC 的。但我后来把样例改成"准考证号首位带 0"的本地测试数据，程序瞬间就崩了。原因是scanf("%lld")读入 010 开头的字符串，会把它当十进制 10，前导零直接消失，输出自然对不上号。这件事给我留下很深印象：标识符一律当字符串，不是开玩笑的。

第二个问题是换行符的坑。在循环里读 M 个查询座位号时，最后一行可能是

3 101 102 103

每两个数之间用空格分隔，最后一个数后面有换行。如果我用 for 循环scanf("%d", &x)读 M 次，完全没问题，换行符会被自动跳过。但如果有人在同一个程序里混用 scanf 和 getchar，那就会多读到一个\n或者空格，导致逻辑错乱。解决办法是：在需要读字符的场景避免和 scanf 混用，或者读完之后手动把缓冲区的换行吸收掉。

5.2 常见问题速查表，直接保存

这张表里的问题，很多不是这一道题独有的，而是几乎所有涉及"字符串 + 数组 + 循环读入"的题目共通的。保存下来，后续刷 L1 题单用到字符串的题都能对号入座。

5.3 考场上最容易忽略的读题细节

还有一点值得提醒：题目要求输出"准考证号和考试座位号"，不包括试机座位号。有的同学写嗨了，顺手把三个字段全打出来，然后对着 Wrong Answer 百思不得其解。这种失分最可惜。建议提交前再读一遍输出格式，尤其是这种字段较多的题目，拿样例输出的格式和自己代码的输出逐字符比对一下，包括空格和换行。

另外，M 个查询座位号有可能重复吗？理论上不会，因为每个坐位只有一个考生，实际测试数据也不会给重复查询。但就算重复，我们的解法也没问题，重复查询就重复输出同样结果。不会有副作用。

6. 映射思想才是这道题真正留给你的东西

6.1 从考试座位号到现实的签到系统

这道题做完了，如果你只记住"试机座位号当下标"这一个trick，那收获还是有点浅。往深想一想，这种"用一个整数键直接索引对应记录"的模式，在真实系统里到处都是。

比如公司门禁系统，工号是整数，刷卡之后后台查员工信息，底层如果数据量不大，完全可以用工号直接映射到内存里的一个结构体数组。再比如图书馆座位预约，座位编号也是整数，系统里需要快速返回"这个座位有没有被预约、预约人是谁"，同样是用座位号做key。还有模拟比赛时用到的参赛编号、医院候诊的诊室号，都是同一套思路。

这个模式的专业术语叫直接寻址表，是哈希表最朴素的原型。理解了它，后面再学到哈希表、unordered_map、字典、对象属性查询，都会觉得不陌生，因为它们都是"根据一个键快速找到对应值"的变体。考试座位号这道题，就是给这个思想打的第一根桩。

6.2 进一步扩展练习的三个方向

如果做完 L1-005 还想趁机多学一点，我可以给三个扩展方向。

第一个方向是题目变形：如果输入的试机座位号不是连续整数，而是随机乱序的编号，比如 10086、20001、30045 这种，用连续数组还可行吗？可行，但是数组要开很大，可能浪费空间，这时候就该考虑用哈希表。用 C 语言的话可以手写一个简单的取模哈希，用 Python 就直接用字典，这两种做法都值得练一练。

第二个方向是数据规模升级：如果 N 变成 10^5，M 也变成 10^5，暴力遍历 O(N*M) 就要爆炸了，而映射法依然能轻松扛住。你可以用这道题的输入生成器构造一大组数据，然后对比两种解法在时间上的差距，顺便测一测自己机器的性能阈值。

第三个方向是语言特性对比：同样的映射逻辑，用数组、结构体、字典、unordered_map 分别实现一遍，观察代码风格和执行效率的差异。这个过程比盲目刷十道简单题更有训练价值，因为你在控制变量的前提下感受了不同抽象层级的表达能力。

6.3 再三强调：越是简单题越要认真读题

最后说一句扎心的经验：L1 题单选座号这类"15分题"其实是整场比赛的保底分。很多人觉得简单就轻视它，结果栽在字符串类型、输出格式、数组越界这些看起来不值得犯的错上。比赛比到最后，高手和普通人之间的差距往往不是难题，而是简单题的稳定率。

我在刷天梯赛题单的时候给自己定过一个规矩：所有 L1 题目，无论多简单，都先把输入输出格式用荧光笔标出来，再动手写代码。这习惯帮我省下的分，远比我多刷十道难题带来的收益大。这道"考试座位号"虽然只有 15 分，但它代表的那类"输入输出清晰、数据结构直观"的基础题，恰恰是最应该拿满分的题型。

如果你顺着这篇文章把代码敲了一遍、把两种语言都试了试、再按扩展方向自己改了几版，那这 15 分的题目在你手里就已经完成了它的教育使命。后续刷到 L2、L3 那些绕弯子的题时，你会发现，真正支撑你快速调通代码的，还是这些基础题里练出来的对数据组织的直觉。