企业官网建设流程全解析

PAT 乙级 1041，题名《考试座位号》，是我觉得整个乙级题库里最适合用来建立“查表思维”的一道题。题面像极了教务系统里的一个小功能：每个考生有准考证号、试机座位号、考试座位号三条信息，有人考试当天迟到，只记得自己的试机座位号，你得从录入的数据里把他对应的准考证号和考试座位号找出来。听上去毫无难度，可它恰恰是算法里最常用的操作——按一个键去取一个值——的原始模型。

这篇文章不打算只贴一段能 AC 的代码，而是把题意拆开、把从暴力到最优的演进过程讲清楚，再把我在提交过程中看到的高频错误一起整理出来。适合刚开始刷 PAT 乙级、准备考研机试或找工作笔试的朋友，也适合那些能过题但想搞清楚“为什么这样写最稳”的读者。全文用到的知识点只涉及数组、字符串和一点点复杂度直觉，对新手非常友好。

1. 题意拆解：迟到考生到底要你查什么

1.1 题面还原成一张现实中的考生信息表

题目描述很朴素：考试前，系统给每位考生分配了两个座位号，一个是试机座位号，一个是考试座位号。考生入场时先用试机座位号找到自己试机的位置，正式考试时再按考试座位号入座。问题出在迟到的考生身上——试机已经结束，他只知道自己之前拿到的试机座位号，现在需要你根据这个号码，查出他的准考证号和考试座位号。

输入格式分两段。前半段是 N 条考生记录，N 不超过 1000，每条记录长得像这样：准考证号、试机座位号、考试座位号。后半段是 M 个待查询的试机座位号，M 也不超过 N。输出要求很死板：每查一个试机座位号，就输出一行，先是准考证号，再是考试座位号，中间一个空格。

说句实话，第一眼看到这个题，大多数人的反应就是“存下来，然后查”。这个直觉没错，但问题在于查的方式。你是一行一行遍历去找，还是直接定位到目标，这是整道题的灵魂。

1.2 输入输出里三个容易被忽略的信号

有些细节不仔细看会吃大亏。

第一，准考证号是 16 位数字。很多第一次刷题的人看到“数字”两个字，下意识就用 int 存，结果要么编译报错，要么运行结果完全不对。这个后面我会专门展开讲。

第二，试机座位号和考试座位号的范围是 1 到 N，注意起点是 1，不是 0。这意味着你如果开数组做映射，数组下标要从 1 开始对齐，数组长度至少是 N+1 而不是 N。

第三，M 个待查询的试机座位号可能写在同一行，也可能跨行，中间的空格和换行都不固定。但只要你用 cin 或者 scanf 读整数，这个问题就完全不存在——标准输入流会自动跳过所有空白字符。很多新手会纠结这里，其实完全没必要。

1.3 考点定位：这题考的是“映射”而不是“查找”

很多人把这道题归类为“模拟题”，因为它没有复杂算法。但我更愿意说它考的是“映射”这两个字。

什么叫映射？就是给一个输入，给你一个输出。试机座位号是键，准考证号和考试座位号是值。你要做的事就是建立键到值的对应关系，并且能在查询时快速取回。

这里引出一个非常重要的概念：哈希表（Hash Table）。哈希表的核心思想是，通过一个函数把键直接换算成存储位置，从而让查找时间从遍历的 O(N) 降到 O(1)。而这道题所谓的“函数”，就是数组下标本身。因为试机座位号正好是连续的整数 1 到 N，所以数组天然就是一张哈希表，取模、冲突都省了。

1.4 这道题到底适合拿来练什么

说白了，1041 是典型的“查表题”教学模型。查表这个操作，在真实开发里无处不在：根据用户 ID 查账号信息、根据订单号查物流状态、根据学号查成绩。这些东西底层全都是同一套逻辑：建表、查表。

1041 把所有干扰信息都剥离干净，只给你最纯粹的键值映射，所以特别适合用来建立“看到键就想到哈希”的条件反射。它不像后面的很多题那样需要你绞尽脑汁设计算法，你只需要把数据结构选对，代码自然就短了。

2. 从暴力到映射：四种写法背后的复杂度账

2.1 暴力解法：能拿满分，但别把它当标准答案

第一种写法，也是最容易想到的写法：把所有考生信息存进结构体数组，每次查询就从头到尾遍历一遍，找到匹配的试机座位号就输出。

#include <iostream> #include <string> using namespace std; struct Student { string id; int testSeat; int examSeat; }; int main() { int N; cin >> N; Student stu[1005]; for (int i = 0; i < N; i++) { cin >> stu[i].id >> stu[i].testSeat >> stu[i].examSeat; } int M; cin >> M; while (M--) { int q; cin >> q; for (int i = 0; i < N; i++) { if (stu[i].testSeat == q) { cout << stu[i].id << " " << stu[i].examSeat << "\n"; break; } } } return 0; }

这段代码提交上去，照样是满分的。原因在于题目数据范围给了你偷懒的空间：N 最大 1000，M 最大也是 1000，最坏情况下的比较次数是 100 万次。现代 CPU 处理 100 万次字符串和整数的比较，耗时基本可以忽略。

但你要清楚，这种“能过”只是题目数据弱。一旦哪天你把同样的思路搬到别的地方，数据范围变成 10 万甚至百万级别，这种 O(N*M) 的写法会瞬间超时。暴力解法在这道题里是合法的，但它不应该成为你的思维方式上限。

2.2 结构体数组：代码整洁了，复杂度纹丝不动

用结构体打包数据，比起松散地管理多个变量，确实让代码清晰不少。从工程规范的角度看，这是一种进步。

但在算法层面，结构体数组加遍历查找，复杂度依然是 O(N*M)。你做了一次查询，最坏要把 1000 条记录全部翻一遍。做 1000 次查询，就是 100 万次比较。

我见过不少同学，提交通过之后就觉得“这道题就这样了”，回头连自己用的是线性查找都不清楚。如果只是追求 AC，没有毛病；但如果想真正提高，就应该多想一步：有没有办法查询时只做 O(1) 的工作？

2.3 数组下标映射：座位号连续是天然哈希表

突破点就在题目里那句不起眼的话：座位号从 1 到 N 编号。

既然试机座位号是连续整数，为什么不用它做数组下标呢？比如我开两个数组：

string id[1005]; // id[试机座位号] = 准考证号 int exam[1005]; // exam[试机座位号] = 考试座位号

读入记录时，让数组和数据在同一个位置对齐：读到一个考生的试机座位号是 5，就把准考证号存进 id[5]，考试座位号存进 exam[5]。查询时给定试机座位号 q，直接输出 id[q] 和 exam[q] 就行。

整套查询过程不涉及任何遍历和比较，时间复杂度就是 O(1)。数据量小的时候，你感知不到数组映射和暴力的差别；数据量一大，差距就是秒杀和超时的区别。

我用一个生活例子解释这件事：暴力查找相当于你在 1000 个快递柜前挨个问“这个包裹是不是你的”；数组映射相当于每个柜门都写了编号，人家报个 5 号，你直接走到 5 号柜掏出包裹。

2.4 四笔账算清楚：查询时间从秒级到纳秒级

下面这张表，是我做题时习惯在草稿纸上列的复杂度分析。

注意看最后一行，map 的查询是 O(log N)，也就是每次查询约 10 次比较，看起来也挺快。但它的建表过程有额外开销，且需要比较节点。在 1000 的数据量下，map 和数组的差距不明显，可数组无论从速度、内存还是代码简洁度上都是最优选择。

这道题就是为了让你明白一个朴素的道理：能用连续下标，就别遍历。

3. 标准解法完整代码与逐行拆解

3.1 C++ 数组映射版：二十行解决的问题

下面是我个人最推荐的标准写法，短小、直接、不容易错。

#include <iostream> #include <string> using namespace std; const int MAXN = 1005; string id[MAXN]; // id[试机座位号] = 准考证号 int exam[MAXN]; // exam[试机座位号] = 考试座位号 int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; for (int i = 0; i < N; i++) { string stuId; int testSeat, examSeat; cin >> stuId >> testSeat >> examSeat; id[testSeat] = stuId; exam[testSeat] = examSeat; } int M; cin >> M; for (int i = 0; i < M; i++) { int q; cin >> q; cout << id[q] << " " << exam[q] << "\n"; } return 0; }

这段代码的关键就两行：id[testSeat] = stuId 和 exam[testSeat] = examSeat。第一次看可能觉得“这不就是把数据挪了个位置吗”，没错，建表本质上就是“按照键来放置值”。

至于输出时的 "\n" 而不是 endl，纯粹是出于习惯。endl 会强制刷新输出缓冲区，在频繁输出时会慢一点点，虽然这道题里根本感觉不到，但养成用 "\n" 的习惯，对你以后刷输出量大的题目有帮助。

3.2 准考证号的数据类型：string 还是 long long

这是这道题最容易翻车的地方，值得单独讲透。

准考证号由 16 位数字组成。先看 int：int 通常能表示的范围大约是 -21 亿到 21 亿，也就是最多 10 位十进制数。16 位数字往 int 里塞，直接溢出，轻则变成一堆莫名其妙的负数，重则运行结果就完全错乱。

再看 long long：它能表示到 19 位十进制数，16 位数字放进去没问题。看似可行，但坑在“前导零”。如果某个准考证号是 0123456789012345，你把它读进 long long，就只剩下 123456789012345，最前面的 0 丢了。题目的输出要求是原样输出准考证号，你用 long long 存，就可能在输出时短一位。

所以最稳妥的做法是用字符串 string 存储，每个字符都保留，输出也完全原样。这也是为什么标准解法里我选了 string 而不是 long long。网上很多旧代码用 long long 也能过，是因为测试数据里没有前导零的情况，但你自己写的时候没必要赌这个。

3.3 数组边界与下标起点：1005 的讲究

数组设计成 MAXN = 1005，不是随便写的。

座位号范围是 1 到 N，N 最大 1000。你要保证能访问到 id[1000]，所以数组长度至少是 1001。开成 1005 属于刷题界的标准余量操作——多开三五个元素，内存几乎不增加，但能避免各种边界问题的焦虑。

还有一点要注意：因为座位号从 1 开始，id[0] 和 exam[0] 就空着了。这是好事，查询时不会出现偏移误差。有些人习惯数组下标从 0 开始，于是非要 offset 一下，搞什么 id[q-1]，完全没必要。这题的键本来就是 1 到 N，直接用对应位置，逻辑最清晰。

3.4 C 语言版本：字符串复制与结束符

如果你用 C 语言写，思路一样，只是字符串处理要多留个心眼。

#include <stdio.h> #include <string.h> char stuId[1005][17]; // 16 位数字 + '\0' int exam[1005]; int main() { int N; scanf("%d", &N); for (int i = 0; i < N; i++) { char tmp[20]; int testSeat, examSeat; scanf("%s %d %d", tmp, &testSeat, &examSeat); strcpy(stuId[testSeat], tmp); exam[testSeat] = examSeat; } int M; scanf("%d", &M); for (int i = 0; i < M; i++) { int q; scanf("%d", &q); printf("%s %d\n", stuId[q], exam[q]); } return 0; }

二维字符数组的第二维必须是 17，因为 16 位数字之外还要留一个位置给字符串结束符 '\0'。scanf 用 %s 读入时会自动在末尾补上结束符，strcpy 复制时也会带上，这里不需要手动处理，但你要理解背后的道理，否则以后碰字符串题目容易出 bug。

4. 踩坑复盘：三个让 AC 率骤降的细节

4.1 十六位数字塞进 int：溢出后的诡异表现

我在刷题群里见过无数次类似的代码片段：int id; 然后往里面读准考证号，输出的时候发现数字变得特别长，或者前几位莫名其妙变成负数。

这就是整数溢出的典型表现。int 只能装下大约 21 亿的绝对值，超出后会发生回绕（wrap around），相当于二进制位被截断，再用十进制解释时就成了完全无关的数。

还有同学用 long long 读，AC 之后跟我炫耀“看我用 long long 也能过”。我只能说，题目的测试数据没有前导零，你运气好。但如果你去参加机试，数据边界一收紧，这种写法就悬了。建议所有字符串编号都默认用 string，这是最不会出错的选择。

4.2 考试座位号来查表：键用错，全盘皆输

题目说的是“给你试机座位号，让你查准考证号和考试座位号”。有些同学读题不仔细，建表的时候把考试座位号当下标，把试机座位号当内容，查询时还拿试机座位号去搜考试座位号数组，结果自然是找不到或者输出错乱。

这种错误在逻辑上很“低级”，但经常发生，尤其在你赶时间的时候。我自己的习惯是，先不急着写代码，在草稿纸上把键和值的关系画出来：

试机座位号 → 准考证号 试机座位号 → 考试座位号

两个映射共用同一个键，查询键始终是试机座位号。动笔之前花 30 秒确认这一点，能帮你省下不少调试时间。

4.3 数组大小开成 1000：越界不报错的隐患

如果你写 int exam[1000] 而不是 [1005]，代码编译没报错，运行也可能“正常”，因为 C++ 对数组越界的行为是未定义——它可能恰好没碰到敏感内存，也可能悄悄覆盖掉相邻变量的数据，让你调试到怀疑人生。

座位号最大是 1000，数组大小 1000 的话，合法下标就是 0 到 999，访问 exam[1000] 已经越界了。一旦查询输入了 1000，你的程序就在读写一块不属于你的内存。

这个问题在本地运行时不一定会暴露，但在判题系统上就可能随机出 WA 或运行时错误。解决的办法很简单：数组开大一点，1005 就是干这个用的。

4.4 再往深一层：如果座位号不是连续编号怎么办

1041 给了连续的座位号，所以数组下标映射是最优解。但如果哪天题目改成“座位号是一个 10 亿以内的大整数，且只有 1000 个考生”，你就不可能开一个 10 亿大小的数组了。这时候的方案是哈希表容器，比如 C++ 的 unordered_map。

#include <iostream> #include <string> #include <unordered_map> using namespace std; int main() { int N; cin >> N; unordered_map<int, pair<string, int>> mp; for (int i = 0; i < N; i++) { string s; int a, b; cin >> s >> a >> b; mp[a] = {s, b}; } int M; cin >> M; for (int i = 0; i < M; i++) { int q; cin >> q; cout << mp[q].first << " " << mp[q].second << "\n"; } return 0; }

unordered_map 的平均查询也是 O(1)，只是常数比数组下标大，而且额外占内存。这就是“通用方案”和“特化方案”的区别。你在 1041 这道题里用数组，不是因为它简单，而是因为你发现了键的连续性这个性质。

5. 从 1041 延伸到一类查表题的通用套路

5.1 三招识别“查表题”

第一，题面里通常有“根据某个编号查询某条信息”这样的描述，而且查询次数往往明显多于信息条数。第二，键通常是整数编号，比如学号、工号、座位号、订单号。第三，输出的结果是一条或者多条与键绑定的记录。

如果你在考试时遇到这种题，第一反应不应该是“遍历匹配”，而是“我应该建一张什么表”。这个思维转变，是乙级刷题过程中很重要的一次升级。

5.2 键的不同形态决定容器的选择

查表题真正考验的是你根据键的特点选容器的能力。

选容器的时候，先问自己三个问题：键是不是整数？键的范围有多大？对输出顺序有没有要求？答案出来，容器基本就定了。

5.3 刷题之外的三点真正有用的习惯

第一，动手前先看数据范围。N 是 1000 还是 10 万，直接决定了你能不能写暴力。看数据范围不是玄学，是算法设计的起点。

第二，能用数组就别过度设计。很多人一听说“映射”就上 map，实际上连续整数用数组更稳、更快。把最简单有效的方案放在脑海里优先级最高的位置，这是高质量工程代码的基本素养。

第三，AC 之后别急着庆祝。花十分钟再想想：如果数据量扩大一千倍，我的写法还成立吗？如果不成立，改进方案是什么？每道题都这样追问一遍，比闷头刷二十道新题都管用。

最后说点我自己的体会。1041 我刷过不止一遍，第一遍用的暴力，当时也觉得“就这”。后来把数据范围擅自改大到十万跑了一次，才发现线性查找慢得不可忍受。回头重写数组映射版，才真正明白题面里那句“座位号 1 到 N”不是随便写的，而是题目给你留的一条捷径。从那以后，我养成了先看取值范围、再定数据结构的习惯。如果你也想系统刷 PAT 乙级，我建议把 1041 当作查表题的模板，先把这一题的所有写法都吃透，后面遇到同类型的成绩查询、身份匹配题，基本就是换个壳而已。