1. 问题引入从日常出行到算法模拟坐公交地铁用优惠券或者免费换乘这是我们很多人每天都会遇到的场景。但你想过没有如果让你用程序来模拟这个过程你会怎么做这不仅仅是写几行代码那么简单它考验的是你如何将现实世界中看似琐碎的规则转化为计算机能精确执行的逻辑。这正是CSP-J2019普及组第二题“公交换乘”的核心魅力所在。这道题源自《信息学奥赛一本通》的1983号题目同时也是洛谷 P5661。它没有复杂的图论或动态规划就是一个纯粹的“模拟题”。但千万别小看“模拟”它往往是区分选手基本功是否扎实的关键。题目要求你根据给定的公交和地铁乘坐记录结合“优惠换乘”规则计算出实际的总花费。规则听起来简单坐地铁后45分钟内坐公交如果公交票价不超过地铁票价就可以免费。但魔鬼藏在细节里——如何高效地管理45分钟的时间窗口如何处理可能“过期”的优惠凭证如何确保每次消费都优先使用最“老”的优惠这些细节正是模拟题的坑点所在。很多初学者一看到题目描述觉得思路清晰上手就写结果要么超时要么答案错误调试起来一头雾水。这道题就是一个典型的“思路简单实现易错”的案例。它考察的不仅仅是编程语法更是严谨的逻辑思维、对数据结构的灵活运用以及边界情况的处理能力。接下来我们就一起拆解这道题看看如何从零开始构建一个既高效又正确的解决方案。2. 规则拆解与核心矛盾分析在动手写代码之前我们必须像法官审阅法条一样把题目规则逐字逐句吃透并找出其中隐含的“矛盾”或“陷阱”。2.1 规则原文精读题目规则可以提炼为以下几点消费类型每次出行记录包含三个信息type0代表地铁1代表公交、price票价、time从当天0点开始经过的分钟数。地铁规则乘坐地铁时必须直接支付全款票价。同时这次乘坐会产生一张优惠凭证。这张凭证包含两个关键属性获得时间即本次乘地铁的time和面值即本次地铁的price。公交规则乘坐公交时首先尝试使用“优惠券”免费乘坐。使用优惠券的条件非常严格时间条件当前公交的乘车时间bus_time必须在某张优惠券的获得时间coupon_time之后的45分钟之内即bus_time - coupon_time 45。金额条件当前公交的票价bus_price必须不超过该优惠券的面值coupon_value即bus_price coupon_value。使用原则如果有多张符合条件的优惠券必须优先使用获得时间最早的那一张。消耗性每张优惠券一旦被使用立即作废。失败处理如果找不到任何一张满足上述时间和金额条件的优惠券那么本次公交乘坐就需要直接支付全款票价。2.2 核心矛盾与算法选择理解规则后我们立刻能发现几个需要程序解决的矛盾查找与匹配每次坐公交都需要从一堆“活着的”优惠券中找到那张“最早获得”且“时间未超时”、“金额够用”的券。这是一个典型的条件筛选排序问题。动态失效优惠券的有效期是动态的。随着时间推进一些较早的券会“过期”超过45分钟。我们需要一种机制来及时清理这些无效券避免对后续查找造成干扰。高效性题目数据规模是n 10^5。如果我们每次坐公交都遍历所有历史优惠券最坏情况O(n^2)在10^5的数据量下极有可能超时Time Limit Exceeded。因此算法效率是必须考虑的重点。基于以上分析一个高效的解决方案需要做到用一种数据结构来存储所有“未使用且未过期”的优惠券。该数据结构要能支持我们快速找到“获得时间最早”的券。要能方便地移除已经使用或过期的券。这自然让我们联想到队列Queue的概念。队列“先进先出”的特性正好符合“优先使用最早获得的券”的规则。我们可以维护一个“优惠券队列”。但普通的队列无法处理“金额条件”和“动态过期”问题因此我们需要一个更灵活的“容器”。3. 数据结构设计与算法思路详解直接使用标准队列行不通因为公交消费时我们可能“跳过”队头那张金额不足的券去使用后面一张金额足够的券吗规则明确禁止这样做必须优先使用最早获得的、且符合条件的券。如果最早的这张券因为金额不足而不能用那么这次公交消费就不能使用任何优惠券即使后面有券符合条件必须付钱。这个规则决定了我们算法的核心流程对于每次公交消费我们从最早的优惠券开始依次检查直到找到第一张同时满足时间和金额条件的券。如果找到就用掉它将其从容器中删除如果检查过程中发现某张券已过期或者所有券都检查完了也没找到合适的那么本次公交就需要付费。3.1 数据结构数组模拟队列 双指针这是本题最经典和高效的做法。我们并不需要真的动态删除数组中间的元素那样效率低而是用数组配合两个指针来模拟一个“滑动窗口”。coupon_time[i],coupon_value[i]: 用两个数组分别存储第i张优惠券的获得时间和面值。数组大小开到n最多10^5即可。head: 队头指针指向当前待检查的最早的优惠券索引。tail: 队尾指针指向下一个优惠券可以存放的位置索引也就是当前队列的长度。初始时head 0,tail 0。used[i]: 一个布尔数组标记第i张优惠券是否已被使用。这是关键因为我们可能跳过一些券金额不足但它们还在“队列”中我们需要标记它已失效后续检查时快速跳过。这个结构就像一个“传送带”。tail是入口每坐一次地铁就生产一张新券放在tail位置然后tail。head是检查的起点。检查时我们从head开始向后扫描。3.2 算法流程分步拆解让我们结合一次具体的公交消费走一遍流程初始化总花费total_cost 0。head 0,tail 0。读入一条记录(type,price,time)。如果是地铁(type 0)总花费直接加上price。生产一张优惠券coupon_time[tail] time; coupon_value[tail] price; used[tail] false;tail。如果是公交(type 1)设置一个标志got_free false表示本次是否成功使用优惠券。清理队头过期或已使用的券这是一个非常重要的优化步骤。我们用while循环检查head tail队列不空且满足以下两个条件之一used[head] true券已使用time - coupon_time[head] 45券已过期 只要满足就将head。这个操作确保了head指针始终指向队列中第一个“未被使用且未过期”的券。注意这个清理是在每次公交消费时都做的保证了队列的有效性。顺序查找可用券从当前的head开始向后遍历索引i直到i tail。如果used[i] true跳过。否则检查条件price coupon_value[i]。注意此时时间条件一定满足因为我们在上一步已经清理了过期的券。如果条件满足说明找到了可用的券标记used[i] true设置got_free true并立即break跳出查找循环。这里必须跳出因为规则是使用第一张符合条件的券。结算如果got_free false没找到券则总花费加上price。3.3 为什么这个算法是高效的关键在于head指针的单调递增和每次公交消费时的“清理”操作。每张优惠券最多被head指针“路过”一次当它过期或被使用时head会越过它。每次公交消费的查找过程虽然看起来是遍历但起始点head在不断前进且查找范围是当前所有“存活”的券。整体上所有优惠券被扫描的总次数与总记录数n成线性关系。因此算法的时间复杂度是O(n)空间复杂度也是O(n)完全可以应对10^5的数据量。注意有些初学者会想用queuepairint, int这样的STL队列然后在公交消费时不断弹出队头检查不合适的再塞回去。这不仅是错误的违反了“必须使用最早一张符合条件的券”的规则因为你把不能用的塞回去它就不是最早的了而且效率低下。我们的“数组双指针used标记”方法才是正解。4. 代码实现与逐行解析C版本理解了算法我们来看具体的C实现。我会在关键代码处加上详细注释。#include iostream using namespace std; const int MAXN 100005; // 根据数据范围定义常量 int main() { int n; cin n; int coupon_time[MAXN]; // 存储优惠券获得时间 int coupon_value[MAXN]; // 存储优惠券面值 bool used[MAXN] {false}; // 标记优惠券是否已使用初始化为false int head 0, tail 0; // 队列头尾指针 long long total_cost 0; // 总花费注意用long long防止溢出 for (int i 0; i n; i) { int type, price, time; cin type price time; if (type 0) { // 乘坐地铁 // 乘坐地铁必须付钱 total_cost price; // 获得一张优惠券放入队列尾部 coupon_time[tail] time; coupon_value[tail] price; // used[tail] 默认是false新券未被使用 tail; // 队尾后移 } else { // 乘坐公交 bool got_free false; // 本次是否免费标志 // 关键步骤1清理队头过期或已使用的优惠券 // 这个循环确保head指向第一个“未使用且未过期”的券 while (head tail) { if (used[head]) { // 如果券已使用head直接后移 head; } else if (time - coupon_time[head] 45) { // 如果券已过期时间差大于45head后移 // 注意这里是 45 不是 45。第45分钟时仍然有效。 head; } else { // 遇到第一个既未使用也未过期的券停止清理 break; } } // 关键步骤2顺序查找可用的优惠券 // 从当前的head开始向后查找 for (int j head; j tail; j) { if (used[j]) { // 跳过已使用的券 continue; } // 此时券j一定未过期因为过期券在清理步骤已被head越过 // 只需判断金额条件 if (price coupon_value[j]) { // 找到符合条件的券 used[j] true; // 标记为已使用 got_free true; // 标记本次免费 break; // 必须跳出只用第一张符合条件的券 } // 如果金额不够继续检查下一张券 // 注意这里不能移动head因为这张券金额不足仍然是“存活”的 // 它可能用于满足后续金额更低的公交消费。 } // 关键步骤3根据查找结果结算 if (!got_free) { // 没找到可用优惠券需要付钱 total_cost price; } // 如果got_free为true则什么也不做免费乘坐 } } cout total_cost endl; return 0; }代码要点解析数据类型total_cost使用long long。虽然单次消费不超过10^6总次数n不超过10^5总花费最大可能是10^11远超int的范围约2e9。这是一个经典的陷阱必须用long long。时间判断条件time - coupon_time[head] 45。这里用而不是意味着在第45分钟时差值为45优惠券仍然有效。这是题目描述的隐含条件务必注意。清理循环的位置清理过期券的操作放在每次公交消费的最开始。这保证了我们后续查找的起点 (head) 始终是有效的。如果放在查找循环内部逻辑会变得复杂且容易出错。查找循环中的break一旦找到符合条件的券立即break。这是规则“优先使用最早的一张”的直接体现。如果不break就会错误地使用后面更新的券。used数组的重要性它让我们可以“跳过”那些金额不足的券而不需要物理删除它们。这些券保留在数组中head指针也可能因为它们金额不足而暂时不移动。它们可能在未来的某次公交消费中如果那趟公交票价更低被使用。5. 常见错误与调试心得即便思路正确实现时也容易踩坑。下面是我在教授这道题和调试学生代码时总结的几个高频错误点。5.1 错误误用“弹出-再压入”的队列// 错误示范 queuepairint, int q; // pairtime, value if (type 0) { cost price; q.push({time, price}); } else { bool found false; queuepairint, int temp; while (!q.empty()) { auto [t, v] q.front(); q.pop(); if (time - t 45) continue; // 过期丢弃 if (price v) { found true; // 使用这张券 break; } else { temp.push({t, v}); // 金额不够暂存到临时队列 } } // 把临时队列里的券和原队列剩下的券合并回去...这里逻辑已经混乱 if (!found) cost price; }问题分析这种做法违背了“必须使用最早一张符合条件的券”的原则。当队头券金额不足时你把它拿出来放到临时队列那么队头就变成了下一张券。对于本次公交消费你实际上跳过了这张最早的券去检查后面的券了。这是规则不允许的。正确的逻辑是如果最早的这张券金额不足那么本次消费就不能使用任何优惠即使后面有券金额足够。5.2 错误head指针移动逻辑错误在查找循环中当遇到一张金额不足的券时有的同学会错误地将head移动到j1。// 查找循环内 if (price coupon_value[j]) { ... } else { head j 1; // 错误不能移动head }问题分析head指针的移动只应该由“清理”步骤驱动即券已使用或过期。一张金额不足的券它依然是一张有效的、未过期的券必须留在“队列”中供后续消费查询。如果移动了head就等于把它从候选池里移除了后续更低票价的公交就无法使用它导致错误。5.3 错误时间条件判断不精确// 错误1使用 if (time - coupon_time[head] 45) head; // 错误第45分钟应有效 // 错误2在查找循环内重复判断时间 for (int j head; j tail; j) { if (time - coupon_time[j] 45) continue; // 冗余且低效 // ... }问题分析错误1属于边界条件处理不当。错误2则反映了对算法结构理解不深。既然在公交消费开始时我们已经用while循环将head移动到了第一个未过期的券那么从head到tail-1的所有券在时间上都是有效的因为如果有过期的head会越过它。所以在查找循环内不需要再判断时间只需判断used和金额即可。重复判断是多余的影响效率也增加出错概率。5.4 调试技巧当你的程序输出错误时可以尝试以下方法构造小数据自己设计一些简单的测试用例特别是边界情况。例1一张地铁券紧接着一张票价更高的公交应付费。例2一张地铁券第44分钟坐公交应免费第46分钟再坐同票价公交应付费。例3多张地铁券公交票价比其中一些高比另一些低。打印中间状态在每次消费后打印head,tail,used数组的部分内容以及total_cost人工模拟核对。对比暴力算法写一个最简单的双重循环暴力算法对于每次公交遍历所有历史地铁记录。用随机生成的小规模数据n100运行两个程序对比结果。这是验证优化算法正确性的黄金标准。6. 举一反三模拟类题目的通用解题框架“公交换乘”这道题是模拟题的优秀范例。通过它我们可以总结出解决此类问题的一般性思路。6.1 模拟题四步法精细化建模将题目描述的自然语言规则转化为一条条无歧义的、可执行的逻辑判断语句。像我们之前做的那样列出所有“如果...那么...”的规则。这是最重要的一步决定了你程序逻辑的骨架。识别核心操作与数据结构分析规则中反复出现的操作。本题核心是“按时间顺序存储凭证”和“查找最早符合条件的凭证”。这提示我们需要一个能维护顺序、支持高效查找/删除的数据结构。数组模拟队列、链表、甚至优先队列都是备选需要根据具体规则选择最合适的。设计算法流程用伪代码勾勒出主循环。明确每一步先做什么后做什么。特别注意处理“状态更新”的时机。例如本题清理过期券的操作放在每次公交消费开始时而不是结束时或另外的线程里。处理边界与效率边界时间、索引的边界如45分钟是还是、数据类型的范围int还是long long、容器为空或满的情况。效率分析数据规模估算最坏时间复杂度。如果可能超时思考如何优化核心操作如将O(n)查找优化为O(log n)或O(1)。本题通过维护head指针和used标记将整体复杂度优化到了O(n)。6.2 类似题目推荐掌握本题后可以尝试以下洛谷上的同类模拟题巩固技能P1540 [NOIP2010 提高组] 机器翻译同样需要维护一个定长的“队列”来模拟内存处理“查找”和“替换”逻辑。P2058 [NOIP2016 普及组] 海港维护一个随时间滑动的窗口统计窗口内不同国家的人数需要处理时间的推进和人员的离开。P7071 [CSP-J2020] 优秀的拆分虽然不涉及队列但也是经典的按规则模拟考察二进制表示和严谨的逻辑。模拟题就像搭积木规则就是说明书。你的任务不是发明新算法而是成为一名忠实且高效的“规则执行者”。耐心、细心和对数据结构的敏感度是解好模拟题的关键。这道“公交换乘”题正是锻炼这些能力的绝佳起点。下次当你再看到复杂的规则描述时希望你能像今天一样冷静地拆解、建模然后写出优雅高效的代码。