经典序列题 UVA12150：数组模拟赛车排名变化与冲突检测

UVA12150 LA4216 Pole Position 是一道非常经典的序列处理入门题表面上是赛车排位赛的名次变化还原骨子里考的是“用数组维护一个序列逐个应用变化并检测非法冲突”的基本功。我第一次做这道题时以为要排序或者搞拓扑后来发现根本不复杂但也正因为不复杂很多人反而容易在细节上栽跟头。这篇就来聊聊这道题的完整思路、实现代码以及那些题解里不会明说的坑。1. 这道题到底在干什么题意与核心考点1.1 背景赛车排位赛中的位置变化题面场景很简单一圈比赛结束后每个车手都会相对上一圈产生名次变化。有人从第5升到第2有人从第3掉到第7也有人全程不动。现在题目把每个车手的编号和名次变化量给你要求还原这一圈结束后的完整排名顺序。如果还原过程中发现数据自相矛盾就输出-1。这个“自相矛盾”是整道题的核心。什么情况算矛盾比如某个车手算出来的新位置超出了总人数范围或者两个车手被安排到了同一个位置都属于数据非法。一旦出现这种情况说明给出的变化记录不可能是真实比赛产生的直接判定-1。理解了这个判定逻辑整道题的框架就出来了先假设数据合法按规则填位置填的过程中只要碰到冲突就立刻宣告失败。1.2 输入顺序隐藏的约定我第一次读题时卡了很久因为题目只给了“车手编号”和“变化量”却没说上一圈的排名是什么。后来才反应过来输入行的顺序本身就是上一圈的排名。也就是说输入的第 i 行代表上一圈结束后位于第 i 位的那个车手的信息。这个约定非常容易忽略但它是整道题能够求解的前提。如果没有这个隐含条件每个车手的“原位置”就是未知的变化量再准确也还原不出新排名。一旦意识到输入顺序就是上一圈的位置序列问题就变成了有N个位置初始时第i个位置上的车手编号已知每个车手告诉你要往左或往右挪多少格模拟一遍就行。1.3 位置变化量的符号方向关于 P 的正负含义这里有一个特别容易搞混的细节。很多中文翻译会把 P 描述成“前进或后退了多少位”但如果你按“前进是位置编号变小”的直觉去写公式大概率会WA。按照这道题常见的官方定义P 是位置编号的偏移量新位置 原位置 P。也就是说P 是正数表示位置编号变大了排名反而下降P 是负数表示位置编号变小了排名反而上升。这和中文口语里的“前进”方向刚好相反。我建议不要死记这个符号约定而是用样例去验证方向。找一组简单的输入比如车手2在上一圈排第2位、变化量是1如果按“新位置原位置1”能得到一个合法结果说明题面的 P 就是位置偏移量如果按“原位置-1”去算可能马上就会出现冲突。考试或者比赛时写代码之前先用样例把方向确认清楚能省下很多次无意义的提交。2. 核心思路把上一圈排名当成初始序列来模拟2.1 为什么输入顺序就是上一圈排名很多模拟题都会把“初始状态”作为输入的一部分但这道题不是直接给你一个数组而是把初始状态藏在了输入行的顺序里。为什么题目要这样设计因为它想考察的是“你是否能理解输入行的语义”而不只是机械地读两个整数。具体的做法是准备一个长度为 N1 的数组 ans下标从 1 到 N 表示这一圈结束后的位置。初始时全部填 00 代表“还没有车手占据”。然后从第 1 行读到第 N 行对第 i 行的车手编号 c 和变化量 p 进行处理。因为我们知道这个车手上一圈的位置就是 i所以他这一圈结束后的新位置就是 i p。这里有一个很关键的理解我们根本不需要先把上一圈的排名完整存放起来因为输入行的序号已经天然充当了“上一圈位置”这个角色。边读边算读完一组数据答案也就出来了。这种“输入行号即初始数组下标”的技巧在很多序列类题目里都会出现值得积累下来。2.2 新位置的计算公式与冲突判定假设车手上一圈的位置是 i变化量是 p那么他本圈结束后的目标位置就是pos i p接下来只需要检查三件事pos 是否小于 1如果小于 1说明这个车手跑到了排名之外不合法。pos 是否大于 N如果大于 N同样不合法。ans[pos] 是否已经有其他车手占据如果是说明两个车手抢同一个位置不合法。只要这三项检查任何一个失败整组数据就是非法的最终输出 -1。否则直接把车手编号填入 ans[pos]。为什么一个简单的数组就能完成全部校验因为每个车手只会被处理一次每个车手的目标位置是唯一确定的。如果所有车手的目标位置都合法且互不冲突那么 N 个车手必然恰好占据 N 个不同位置不需要额外检查“是不是所有位置都被填满了”。这一点很多题解不会明说但它保证了算法的正确性也解释了为什么不需要在最后再做一次遍历确认。2.3 时间复杂度与空间复杂度分析整个算法的时间复杂度是 O(N)因为只需要对每个车手做一次常数时间的计算和校验。空间复杂度是 O(N)用于存储 ans 数组。这个复杂度在同类题目里基本属于最优了。你可能觉得 O(N) 没什么好说的但要注意这道题如果换成“先排序再匹配”的思路复杂度会变成 O(N log N)而且排序过程还会破坏输入行的位置语义属于典型的思路绕远。每次看到这种简单题我都习惯先想一下“能不能用一个数组直接模拟”如果可以就不要急着上排序、哈希、并查集那些重武器。3. 完整实现C版与Python版的逐段拆解3.1 C实现与关键代码注释直接上代码。下面这个 C 版本我加了比较详细的注释方便你对照思路看。#include bits/stdc.h using namespace std; int main() { int n; while (cin n n) { vectorint ans(n 1, 0); bool ok true; for (int i 1; i n; i) { int c, p; cin c p; // i 是上一圈位置p 是位置编号偏移量 // 按题目惯例新位置 原位置 p int pos i p; if (pos 1 || pos n || ans[pos] ! 0) { ok false; } else { ans[pos] c; } } if (!ok) { cout -1 \n; } else { for (int i 1; i n; i) { cout ans[i] \n[i n]; } } } return 0; }这里有两处细节要特别说明。第一即使发现 ok 变成 false循环也要继续读入不能提前 break。因为输入流里还有当前这组数据剩下的行如果 break 掉下一组数据就会错位。第二输出时用 \n[i n]控制空格和换行保证行尾没有多余空格这在严格按字节比对输出的 OJ 上能避免一些无谓的 WA。3.2 Python实现与简洁写法Python 版本的逻辑完全一样只是写法上更贴近 Python 的习惯。import sys def solve(): while True: line sys.stdin.readline() if not line: break n int(line) if n 0: break ans [0] * (n 1) ok True for i in range(1, n 1): c, p map(int, sys.stdin.readline().split()) pos i p if pos 1 or pos n or ans[pos] ! 0: ok False else: ans[pos] c if not ok: print(-1) else: print( .join(map(str, ans[1:]))) if __name__ __main__: solve()Python 版有一个天然优势即使检测到冲突后续的 for 循环也会继续读完本组所有行不会出现 C 里手动 break 导致输入错位的问题。另外ans[1:]可以直接从下标 1 截到结尾配合join输出代码干净利落。3.3 边界情况与输出格式细节边界情况主要集中在这几个位置单个车手变化量很大比如 N5第 1 位车手的 p 是 100那么 pos 101越界输出 -1。变化量为负数且绝对值大于原位置比如第 3 位车手的 p 是 -5那么 pos -2越界输出 -1。两个车手目标位置相同比如第 1 位车手 p1第 2 位车手 p0两人都指向位置 2冲突输出 -1。输出格式上每个测试用例占一行N0 表示输入结束。输出 -1 时也要单独占一行不要和其他内容混在一起。有些 OJ 对行尾空格很敏感建议严格按“除最后一个数字外每个数字后跟一个空格”的格式处理。4. 踩坑记录常见错误与调试技巧4.1 数组下标从 0 开始导致的隐蔽越界这是我见过最多的错误。很多人习惯了数组从 0 开始于是开一个长度为 n 的数组下标从 0 到 n-1。但题目里排名是从 1 到 n位置编号也是从 1 开始。如果还按 0-based 的思想写pos i p当 pos 等于 n 时数组访问就越界了。解决方法是统一采用 1-based 下标。要么开 n2 长度的数组要么在计算 pos 后主动检查范围。我个人推荐前者因为只要数组长度够配合显式的pos 1 || pos n判断就不太容易出现隐蔽的越界问题。每次写这种模拟题我都会先确认“位置编号从几开始”这是在动键盘之前就应该想清楚的事。4.2 符号方向搞反之后怎么快速自查如果你提交后 WA并且怀疑是 P 的正负方向问题最直接的方法是构造一个非常小的测试用例比如 N22 1 0 2 -1如果按pos i p计算车手2从第2位变成第1位最终排名是 2 1合法。如果你写成了pos i - p车手2会变成第3位越界输出 -1。拿这种只有两三个车手的最小样例去验证方向效率远高于盯着代码空想。我自己就曾经在符号方向上栽过一次。那次我自信满满地写了i - p总觉得“正数就是前进”结果样例一跑就发现第一位和第二位冲突才意识到方向理解反了。从那以后我遇到任何带“变化量”的题目都会先拿最小样例把公式验证一遍再开始写完整逻辑。4.3 多组输入的初始化与终止条件这道题有多组测试用例读入直到 N0 结束。最容易犯的错误是忘记在每组新数据开始时重置 ans 数组。如果在循环外定义 ans每组都要手动清零如果在循环内定义就会自动重新初始化。我的建议是直接在循环内定义 vector这样不可能出现上一组残留数据影响下一组的情况。还有一个细节N0 是终止条件但题目并没有保证 N 一定是正数。如果用了类似while (cin n, n)的写法要确保只读一个整数就判断不要多读东西。输入终止之后程序要正常退出不能继续等数据。4.4 手搓对抗样例的调试思路调试这种模拟题最快的办法不是单步调试而是手搓几个对抗性样例。我常用的组合是一个完全合法的样例比如所有 p 都是 0输出应该和输入顺序一致。一个越界样例比如某个车手直接跳到第 N 位之外。一个冲突样例比如两个车手都指向同一个位置。一个负数越界样例比如第一个车手的 p 是 -1。把这四个样例跑通基本上代码的核心逻辑就没有问题了。如果还想更稳可以加一个“暴力验证器”生成随机排列和合法变化量用另一个数组模拟移动然后对比你的核心代码输出是否一致。这种对拍思路在复杂模拟题里非常实用这道题虽然简单但用来练习对拍也完全不亏。5. 这类题还能怎么考扩展与变体5.1 如果允许环形移动怎么办这道题的位置是线性的越界就非法。但如果把场景改成循环赛道比如某些赛车游戏里位置绕一圈回到起点那么计算就变成pos ((i p - 1) % n n) % n 1。这种情况下越界检查会被取模运算替代但“位置冲突”的判定依然保留。环形版本的题目在思维上多了一个弯位置编号需要归一化同时要小心负数取模在部分语言里的坑。建议先把线性版本彻底想通再去挑战环形版本因为核心的冲突检测逻辑是完全一致的。5.2 类似序列处理题的迁移思路“按输入行号确定初始位置逐个应用变化量用数组检测冲突”这个模式可以迁移到不少场景。比如多台服务器调整负载均衡配置每个服务迁移到新的节点会议室排期调整每场会议换到新的时间段数据库表结构调整每条记录移动到新的分片。本质都是“初始状态已知每个元素给出目标位置检测唯一性和合法性”。掌握这种迁移思路比单纯记住一道题的答案有价值得多。以后遇到任何看起来像“位置重排”的题目第一反应都应该是能不能用一个辅助数组标记目标位置如果能马上往这个方向思考。5.3 竞赛中的实用经验最后分享几个适用于所有模拟题的竞赛经验。第一不要急着写代码先用一两分钟把输入格式和样例推演清楚。很多模拟题的坑都藏在输入语义里而不是算法复杂度上。第二能用数组就用数组不要硬套高级数据结构。这道题如果非要用 map 或 set 去存车手位置代码会变得又慢又难调。第三输出之前检查一下是否多输出空格、少输出换行这类格式问题在 OJ 上会直接判 WA。我个人刷题的习惯是每道模拟题做完之后把“核心数组 冲突条件”用一行注释写在代码最上面。下次回看时几分钟就能重新想起来这道题到底在考什么。这种整理方式对复习和建立题感都很有帮助。