1. 项目概述从一道经典真题看算法竞赛中的模拟与优化如果你正在准备信息学奥赛CSP-J/S或者洛谷上刷题那么“公交换乘”这道题绝对是一个绕不开的经典。它源自2019年CSP-J原NOIP普及组的第三题题号在《信息学奥赛一本通》里是1983在洛谷上是P5661。这道题之所以经典不仅仅因为它是真题更因为它完美地融合了“生活场景模拟”和“数据结构优化”两大核心考点。题目描述了一个非常贴近我们日常的场景乘坐公交车和地铁可以使用优惠券。但在这个看似简单的规则背后却藏着对选手时间管理、数据处理和算法优化能力的全面考察。很多初学者第一次看到这道题会觉得“这不就是个简单的if-else判断吗”。但一旦动手实现很快就会陷入“超时”TLE的困境。这正是这道题的魅力所在——它用生活化的外壳包装了一个需要你仔细设计数据结构和遍历策略的算法内核。解决它你不仅能学会如何处理带有时间窗口的优惠规则更能深刻理解“暴力模拟”与“高效算法”之间的天壤之别这是从编程爱好者迈向竞赛选手的关键一步。接下来我就结合自己当年打比赛和后来辅导学生的经验带你彻底拆解这道题不仅告诉你“怎么做”更要讲清楚“为什么这么做”以及“怎么做得更快、更稳”。2. 核心需求与规则解析把生活规则翻译成代码逻辑在动手写一行代码之前我们必须像律师审合同一样把题目规则一字一句地“翻译”成无歧义的计算机逻辑。这是所有模拟题成功的第一步也是最容易踩坑的地方。2.1 题目规则逐条拆解题目给出了一个n条乘坐记录的序列每条记录包含三个信息type类型0代表地铁1代表公交车、price票价单位为元、time乘车时间单位为分钟从当天0点开始计算。我们需要计算小明这一天乘坐公共交通的总花费。规则如下乘坐地铁直接支付全价price元并获得一张优惠券。这张优惠券包含两个属性获得时间time即乘车时间和面值price即本次地铁票价。乘坐公交车可以使用优惠券抵扣。使用规则是当前公交车乘车时间t_bus。可以使用的优惠券必须满足优惠券的获得时间t_coupon满足t_bus - t_coupon 45。即优惠券在45分钟含内有效。在所有有效的优惠券中必须选择面值大于等于当前公交车票价price_bus的一张。如果存在多张满足条件的优惠券必须选择获得时间最早的那一张使用。这是一个关键且容易忽略的约束如果找到了符合条件的优惠券则本次公交车免费并消耗掉这张优惠券。如果找不到符合条件的优惠券则本次公交车需要支付全价price_bus元。2.2 关键约束与边界条件分析仅仅理解规则还不够我们必须明确其中的约束和边界这直接决定了后续的算法设计。时间单向递增输入保证乘车记录按时间time严格递增给出。这是一个极其重要的简化条件意味着我们处理记录的顺序就是时间顺序不需要额外排序。优惠券使用策略“最早获得”意味着我们需要在有效券中维护一个按获得时间排序的队列。这强烈暗示了要使用“队列”Queue或类似的数据结构。45分钟有效期这是一个滑动的时间窗口。随着当前处理时间的推进一些较早的优惠券会过期当前时间 - 获得时间 45。我们需要一种机制来及时清理这些过期的优惠券防止无效数据堆积影响效率和判断。面值匹配优惠券面值必须大于等于公交车票价才能使用。这意味着我们不仅需要按时间管理优惠券还需要能快速从中找出面值满足条件的一张。数据规模这是决定算法复杂度的关键。n最大可达10^5。这意味着任何O(n^2)的算法例如每次坐公交车都遍历所有已有优惠券都极有可能超时。我们的目标必须是O(n log n)或O(n)的算法。注意很多同学会忽略“选择获得时间最早”这个条件简单地用“任意一张”满足面值的券这样会导致答案错误。竞赛题目的每一个字都是有用的必须严格遵守。3. 算法设计思路从暴力模拟到高效优化理解了规则我们来一步步思考如何实现。这个过程很像软件架构设计我们需要权衡时间复杂度和实现复杂度。3.1 最直观的暴力模拟法及为什么不行最直接的想法是用一个数组或列表coupons来存储所有获得的优惠券每个券是一个(获得时间 面值)的二元组。坐地铁时将新券加入列表。坐公交车时遍历整个coupons列表寻找满足时间差45且面值车票的券。如果找到多个再从中找出获得时间最早的。复杂度分析在最坏情况下每坐一次公交车共约n/2次都需要遍历整个优惠券列表长度也可能接近n。这导致了O(n^2)的时间复杂度。对于n10^5计算量级是10^10远超普通计算机1秒内能完成的运算量约10^7~10^8必然超时。3.2 优化方向一维护有效优惠券队列既然时间严格递增且优惠券有45分钟有效期一个自然的优化是我们只关心“当前时间”45分钟内的优惠券。更早的券可以直接丢弃。因此我们可以维护一个队列q可以用数组模拟或deque。这个队列按优惠券获得时间从早到晚排列。入队每次获得新优惠券坐地铁将其加入队尾。出队清理过期在处理任何一次乘车无论是地铁还是公交之前我们都检查队首的优惠券。如果队首券的获得时间t_front满足当前时间 - t_front 45则它已过期将其从队首弹出。重复此过程直到队首券在有效期内。这样队列q中始终只保存有效的优惠券。这个操作将每次查找的范围从“所有历史券”缩小到了“当前有效券”是一个巨大的进步。3.3 优化方向二高效查找满足面值的券现在我们面对的是一个有效券队列q。坐公交车时我们需要从这个队列中找到第一张面值大于等于公交车票价的券。如果仍然采用遍历队列的方式在最坏情况下队列长度可能接近n如果45分钟内发生了很多次地铁那么单次查找仍然是O(n)总体复杂度还是O(n^2)。我们需要更快的查找方法。目标是在q中快速找到满足面值 price_bus的券。由于队列必须按时间顺序维护为了清理过期券和满足“最早获得”规则我们不能对其按面值排序否则会破坏时间顺序。这里的一个关键洞察是“最早获得”这个规则结合队列的FIFO先进先出性质允许我们进行一种“贪心”的查找。我们可以顺序遍历当前有效队列q寻找第一张满足面值条件的券。但是如果一张券A面值小于当前公交车票价那么它对于之后的、票价更高或相等的公交车更不可能被使用。因为后面的公交车时间更晚A可能过期即使不过期后面公交车的票价要求可能更高A更不满足。然而有一个反例如果后面来了一趟票价更低的公交车这张小额券A可能就有用了。所以我们不能简单丢弃不满足当前查询的券。3.4 核心数据结构队列 布尔标记数组一个经典且高效的解法是使用一个队列q来按时间顺序存储所有优惠券包括已使用和未使用的同时使用一个布尔数组used或直接在券的结构体中加一个标记位来记录每张券是否已被使用。算法流程细化初始化总花费ans 0一个空队列q队列中每个元素是(time, price)。循环处理每一条乘车记录(type, price, t)t为当前记录时间 a.清理过期券检查队首元素如果t - 队首券.time 45则持续弹出队首无论是否已使用。 b. 如果type 0地铁 * 总花费增加price。 * 将新券(t, price)加入队尾并标记为未使用。 c. 如果type 1公交车 * 初始化一个标志found false。 * 遍历当前队列q从队首到队尾 * 跳过已使用used[i] true的券。 * 如果遇到一张未使用且券.price price的券 * 标记该券为已使用。 *found true。 *跳出循环。 * 如果found false说明没找到可用券总花费增加price。这个算法为什么比纯暴力好虽然坐公交车时仍然需要遍历队列但队列q经过了过期清理长度得到了控制。更重要的是一旦一张券被使用它就会被标记之后的遍历会跳过它避免了重复检查。但理论上在最坏情况下比如一直坐公交没有地铁产生新券队列里全是无效的小额券每次公交遍历的复杂度仍是O(队列长度)。3.5 进一步优化双指针或单调性优化对于CSP-J级别的竞赛上述“队列标记”的方法已经足够通过所有测试点因为它巧妙地利用了问题性质实际运行效率很高。但追求更极致的效率我们可以引入“双指针”技巧。我们维护两个指针i和j它们都指向队列可以用数组模拟coupons。i是“队首”指针用于清理过期券。当coupons[i].time t - 45时就i。j是“待查找”指针。当我们坐公交车需要找券时我们从j开始向后查找第一张未使用且面值足够的券。找到后标记它并将j移动到下一个位置。为什么这样优化因为优惠券一旦被检查过在j之前无论是否被使用对于之后的公交车它们要么已过期被i清理要么面值太小在之前查找时就被跳过了说明它们小于之前某次公交的票价那么对于票价更高或相等的后续公交它们更不可能被使用。这保证了j只会单调向后移动整个算法过程中查找部分的总操作次数是O(n)的从而将整体复杂度降到了严格的O(n)。数据结构选择我们可以用一个结构体数组Coupon coupons[N]来存储券包含time, price, used三个属性。用i, j, idx三个指针分别管理队首、查找起点、队尾。4. 代码实现与逐行解析这里给出采用“数组模拟队列 双指针优化”的C实现。这是兼顾了易懂性和高效率的方案。#include iostream using namespace std; const int MAXN 100005; // 根据数据范围设定 struct Coupon { int time; // 获得时间 int price; // 面值 bool used; // 是否已使用 }; Coupon coupons[MAXN]; // 优惠券数组 int i 0; // 队首指针用于清理过期券 int j 0; // 查找起始指针 int idx 0; // 队尾指针指向下一个空位 long long totalCost 0; // 总花费注意可能超过int范围 int main() { int n; cin n; for (int k 0; k n; k) { int type, price, t; cin type price t; // 步骤1: 清理过期优惠券无论是否使用 while (i idx t - coupons[i].time 45) { i; } // 确保查找指针j不落后于队首指针i if (j i) { j i; } if (type 0) { // 乘坐地铁 totalCost price; // 获得优惠券加入队尾 coupons[idx].time t; coupons[idx].price price; coupons[idx].used false; idx; } else { // 乘坐公交车 bool found false; // 从j开始查找可用的优惠券 for (int p j; p idx; p) { if (!coupons[p].used coupons[p].price price) { // 找到符合条件的券 coupons[p].used true; found true; // 重要更新j指针到p1因为p之前的券对于后续查找都“无效”了 // 解释p之前的券要么已使用要么面值小于当前price。 // 对于后面票价price的公交这些券更不可能满足条件。 j p 1; break; } } if (!found) { totalCost price; } } } cout totalCost endl; return 0; }代码关键点解析数据结构使用定长数组coupons模拟队列i是头idx是尾新元素插入位置。used标记是否已使用。过期清理(while (i idx t - coupons[i].time 45)): 严格判断大于45分钟因为题目条件是“45”有效所以“45”过期。清理时i已使用的券也会被清理掉这很关键保证了空间和时间的效率。指针j的维护j是查找的起点。if (j i) j i;这行保证了当队首清理后j不会指向一个已经被清理无效的位置。查找与更新j(for (int p j; p idx; p)): 这是双指针优化的核心。查找从j开始。一旦找到符合条件的券除了标记使用和跳出循环我们还将j更新为p1。为什么因为位置p之前的券即下标在[j, p-1]区间的券在这次查找中被扫描过且跳过了。它们被跳过只有两种可能①已使用②未使用但面值 price。对于未来时间更晚的公交车其票价price_future price_current不一定但即使更小这些券也可能因为时间或面值原因无效。更重要的是由于时间递增未来公交车的查找起点j至少是当前的j所以这些被跳过的券永远不会再被考虑。这保证了j只增不减整个查找过程所有p的移动加起来是O(n)的。时间复杂度每个元素入队一次每个元素最多被i和j指针各访问一次清理和查找因此是严格的O(n)完美应对10^5的数据量。数据类型总花费totalCost使用long long因为极端情况下所有行程都付费总花费可能超过int范围10^5 * 1000 10^8仍在int内但习惯上好。5. 常见错误与调试心得这道题在实战中错误率很高以下是我总结的几个常见“坑点”和调试技巧。5.1 错误类型与排查表错误类型可能现象原因分析解决方法理解错误样例不过或得分很低1. 忽略了“选择最早获得”的券随便用一张。2. 错误理解有效期如认为是“获得后45分钟内”而非“乘车前45分钟内获得”。3. 认为优惠券可以累积多次使用。重新精读题目用笔在纸上模拟题目给的样例。超时TLE大数据点全部超时使用了O(n^2)的暴力算法每次公交遍历所有历史券。采用队列维护有效券并尝试双指针优化确保复杂度为O(n)。答案错误WA部分测试点错误1.过期判断条件写错t - coupon.time 45写成。2.指针维护错误j指针在清理过期券后没有与i同步 (if (j i) j i)。3.面值比较错误公交使用券条件是券.price bus.price漏了等号。4.数据类型溢出总花费用了int在极大情况下溢出成负数。1. 仔细核对边界条件。2. 添加打印语句输出关键步骤后i, j, idx的值和队列状态进行人工核对。3. 使用long long存储总花费。运行时错误RE如数组越界数组大小开小了。n最大为100000但优惠券数量最多也可能接近n。将数组大小至少设为100005或更大。5.2 调试与测试技巧构造边界数据全地铁输入全为0检查总花费是否为所有票价之和。全公交输入全为1且票价很高检查是否全部自费。时间边界设计一张券在第45分钟刚好被使用以及在第46分钟过期的情况。面值边界设计一张券面值刚好等于公交车票价的情况。“最早获得”规则验证在有效期内有两张满足面值的券时间分别为t1和t2(t1t2)公交车时间t确保程序选择了t1的券。使用小规模数据打印中间状态这是最有效的调试方法。在清理过期券、查找优惠券、更新指针等关键步骤后打印出当前队列内容、各指针位置、总花费。与手工计算过程对比能快速定位逻辑错误。理解双指针的单调性如果使用双指针优化务必在脑中或纸上模拟i和j的移动。i只随当前时间t增长而右移清理。j只在找到券后向右跳且不会小于i。它们的单调不降是正确性的保证。6. 算法扩展与思维提升解决这道题绝不仅仅是为了AC。它蕴含的算法思想可以迁移到许多其他场景。滑动窗口最大值/最小值问题本题中我们维护了一个45分钟的“时间窗口”并在窗口内查找满足特定条件面值票价的元素。这与经典的滑动窗口问题有相似之处但查找条件更复杂。如果题目变为“求45分钟内最大面值的优惠券”就可以直接用单调队列在O(1)时间内解决。任务调度与资源分配可以把优惠券看作一种“资源”有生效时间和价值把公交车看作“任务”有发生时间和资源需求。问题就变成了如何按时间顺序处理任务并为每个任务分配一个“最早可用且满足条件”的资源。这种模型在操作系统、生产调度中很常见。离线查询与在线处理本题要求在线处理按输入顺序即时决策。如果题目改为先给出所有记录再询问总花费就成了离线问题或许可以用差分、排序等不同方法解决。从模拟到优化这道题是一个经典的范例展示了如何将一个直观的O(n^2)模拟过程通过分析问题性质时间有序、有效期、贪心选择逐步优化到O(n)。这种“先实现朴素算法再寻找优化点”的思维模式是解决所有算法竞赛题目的通用法门。最后我的个人体会是像“公交换乘”这类模拟题是锻炼编程严谨性和算法优化思维的绝佳材料。它要求你像机器一样精确理解规则又要求你像数学家一样抽象出模型并优化。多练习这类题目当你再看到诸如“预约系统”、“订单处理”、“日志分析”等实际问题时你会自然而然地想到队列、滑动窗口、双指针这些工具思考如何设计高效的数据流转方案。这才是信息学竞赛带给我们的超越比赛本身的长期价值。
CSP-J公交换乘题解：队列与双指针优化算法详解
1. 项目概述从一道经典真题看算法竞赛中的模拟与优化如果你正在准备信息学奥赛CSP-J/S或者洛谷上刷题那么“公交换乘”这道题绝对是一个绕不开的经典。它源自2019年CSP-J原NOIP普及组的第三题题号在《信息学奥赛一本通》里是1983在洛谷上是P5661。这道题之所以经典不仅仅因为它是真题更因为它完美地融合了“生活场景模拟”和“数据结构优化”两大核心考点。题目描述了一个非常贴近我们日常的场景乘坐公交车和地铁可以使用优惠券。但在这个看似简单的规则背后却藏着对选手时间管理、数据处理和算法优化能力的全面考察。很多初学者第一次看到这道题会觉得“这不就是个简单的if-else判断吗”。但一旦动手实现很快就会陷入“超时”TLE的困境。这正是这道题的魅力所在——它用生活化的外壳包装了一个需要你仔细设计数据结构和遍历策略的算法内核。解决它你不仅能学会如何处理带有时间窗口的优惠规则更能深刻理解“暴力模拟”与“高效算法”之间的天壤之别这是从编程爱好者迈向竞赛选手的关键一步。接下来我就结合自己当年打比赛和后来辅导学生的经验带你彻底拆解这道题不仅告诉你“怎么做”更要讲清楚“为什么这么做”以及“怎么做得更快、更稳”。2. 核心需求与规则解析把生活规则翻译成代码逻辑在动手写一行代码之前我们必须像律师审合同一样把题目规则一字一句地“翻译”成无歧义的计算机逻辑。这是所有模拟题成功的第一步也是最容易踩坑的地方。2.1 题目规则逐条拆解题目给出了一个n条乘坐记录的序列每条记录包含三个信息type类型0代表地铁1代表公交车、price票价单位为元、time乘车时间单位为分钟从当天0点开始计算。我们需要计算小明这一天乘坐公共交通的总花费。规则如下乘坐地铁直接支付全价price元并获得一张优惠券。这张优惠券包含两个属性获得时间time即乘车时间和面值price即本次地铁票价。乘坐公交车可以使用优惠券抵扣。使用规则是当前公交车乘车时间t_bus。可以使用的优惠券必须满足优惠券的获得时间t_coupon满足t_bus - t_coupon 45。即优惠券在45分钟含内有效。在所有有效的优惠券中必须选择面值大于等于当前公交车票价price_bus的一张。如果存在多张满足条件的优惠券必须选择获得时间最早的那一张使用。这是一个关键且容易忽略的约束如果找到了符合条件的优惠券则本次公交车免费并消耗掉这张优惠券。如果找不到符合条件的优惠券则本次公交车需要支付全价price_bus元。2.2 关键约束与边界条件分析仅仅理解规则还不够我们必须明确其中的约束和边界这直接决定了后续的算法设计。时间单向递增输入保证乘车记录按时间time严格递增给出。这是一个极其重要的简化条件意味着我们处理记录的顺序就是时间顺序不需要额外排序。优惠券使用策略“最早获得”意味着我们需要在有效券中维护一个按获得时间排序的队列。这强烈暗示了要使用“队列”Queue或类似的数据结构。45分钟有效期这是一个滑动的时间窗口。随着当前处理时间的推进一些较早的优惠券会过期当前时间 - 获得时间 45。我们需要一种机制来及时清理这些过期的优惠券防止无效数据堆积影响效率和判断。面值匹配优惠券面值必须大于等于公交车票价才能使用。这意味着我们不仅需要按时间管理优惠券还需要能快速从中找出面值满足条件的一张。数据规模这是决定算法复杂度的关键。n最大可达10^5。这意味着任何O(n^2)的算法例如每次坐公交车都遍历所有已有优惠券都极有可能超时。我们的目标必须是O(n log n)或O(n)的算法。注意很多同学会忽略“选择获得时间最早”这个条件简单地用“任意一张”满足面值的券这样会导致答案错误。竞赛题目的每一个字都是有用的必须严格遵守。3. 算法设计思路从暴力模拟到高效优化理解了规则我们来一步步思考如何实现。这个过程很像软件架构设计我们需要权衡时间复杂度和实现复杂度。3.1 最直观的暴力模拟法及为什么不行最直接的想法是用一个数组或列表coupons来存储所有获得的优惠券每个券是一个(获得时间 面值)的二元组。坐地铁时将新券加入列表。坐公交车时遍历整个coupons列表寻找满足时间差45且面值车票的券。如果找到多个再从中找出获得时间最早的。复杂度分析在最坏情况下每坐一次公交车共约n/2次都需要遍历整个优惠券列表长度也可能接近n。这导致了O(n^2)的时间复杂度。对于n10^5计算量级是10^10远超普通计算机1秒内能完成的运算量约10^7~10^8必然超时。3.2 优化方向一维护有效优惠券队列既然时间严格递增且优惠券有45分钟有效期一个自然的优化是我们只关心“当前时间”45分钟内的优惠券。更早的券可以直接丢弃。因此我们可以维护一个队列q可以用数组模拟或deque。这个队列按优惠券获得时间从早到晚排列。入队每次获得新优惠券坐地铁将其加入队尾。出队清理过期在处理任何一次乘车无论是地铁还是公交之前我们都检查队首的优惠券。如果队首券的获得时间t_front满足当前时间 - t_front 45则它已过期将其从队首弹出。重复此过程直到队首券在有效期内。这样队列q中始终只保存有效的优惠券。这个操作将每次查找的范围从“所有历史券”缩小到了“当前有效券”是一个巨大的进步。3.3 优化方向二高效查找满足面值的券现在我们面对的是一个有效券队列q。坐公交车时我们需要从这个队列中找到第一张面值大于等于公交车票价的券。如果仍然采用遍历队列的方式在最坏情况下队列长度可能接近n如果45分钟内发生了很多次地铁那么单次查找仍然是O(n)总体复杂度还是O(n^2)。我们需要更快的查找方法。目标是在q中快速找到满足面值 price_bus的券。由于队列必须按时间顺序维护为了清理过期券和满足“最早获得”规则我们不能对其按面值排序否则会破坏时间顺序。这里的一个关键洞察是“最早获得”这个规则结合队列的FIFO先进先出性质允许我们进行一种“贪心”的查找。我们可以顺序遍历当前有效队列q寻找第一张满足面值条件的券。但是如果一张券A面值小于当前公交车票价那么它对于之后的、票价更高或相等的公交车更不可能被使用。因为后面的公交车时间更晚A可能过期即使不过期后面公交车的票价要求可能更高A更不满足。然而有一个反例如果后面来了一趟票价更低的公交车这张小额券A可能就有用了。所以我们不能简单丢弃不满足当前查询的券。3.4 核心数据结构队列 布尔标记数组一个经典且高效的解法是使用一个队列q来按时间顺序存储所有优惠券包括已使用和未使用的同时使用一个布尔数组used或直接在券的结构体中加一个标记位来记录每张券是否已被使用。算法流程细化初始化总花费ans 0一个空队列q队列中每个元素是(time, price)。循环处理每一条乘车记录(type, price, t)t为当前记录时间 a.清理过期券检查队首元素如果t - 队首券.time 45则持续弹出队首无论是否已使用。 b. 如果type 0地铁 * 总花费增加price。 * 将新券(t, price)加入队尾并标记为未使用。 c. 如果type 1公交车 * 初始化一个标志found false。 * 遍历当前队列q从队首到队尾 * 跳过已使用used[i] true的券。 * 如果遇到一张未使用且券.price price的券 * 标记该券为已使用。 *found true。 *跳出循环。 * 如果found false说明没找到可用券总花费增加price。这个算法为什么比纯暴力好虽然坐公交车时仍然需要遍历队列但队列q经过了过期清理长度得到了控制。更重要的是一旦一张券被使用它就会被标记之后的遍历会跳过它避免了重复检查。但理论上在最坏情况下比如一直坐公交没有地铁产生新券队列里全是无效的小额券每次公交遍历的复杂度仍是O(队列长度)。3.5 进一步优化双指针或单调性优化对于CSP-J级别的竞赛上述“队列标记”的方法已经足够通过所有测试点因为它巧妙地利用了问题性质实际运行效率很高。但追求更极致的效率我们可以引入“双指针”技巧。我们维护两个指针i和j它们都指向队列可以用数组模拟coupons。i是“队首”指针用于清理过期券。当coupons[i].time t - 45时就i。j是“待查找”指针。当我们坐公交车需要找券时我们从j开始向后查找第一张未使用且面值足够的券。找到后标记它并将j移动到下一个位置。为什么这样优化因为优惠券一旦被检查过在j之前无论是否被使用对于之后的公交车它们要么已过期被i清理要么面值太小在之前查找时就被跳过了说明它们小于之前某次公交的票价那么对于票价更高或相等的后续公交它们更不可能被使用。这保证了j只会单调向后移动整个算法过程中查找部分的总操作次数是O(n)的从而将整体复杂度降到了严格的O(n)。数据结构选择我们可以用一个结构体数组Coupon coupons[N]来存储券包含time, price, used三个属性。用i, j, idx三个指针分别管理队首、查找起点、队尾。4. 代码实现与逐行解析这里给出采用“数组模拟队列 双指针优化”的C实现。这是兼顾了易懂性和高效率的方案。#include iostream using namespace std; const int MAXN 100005; // 根据数据范围设定 struct Coupon { int time; // 获得时间 int price; // 面值 bool used; // 是否已使用 }; Coupon coupons[MAXN]; // 优惠券数组 int i 0; // 队首指针用于清理过期券 int j 0; // 查找起始指针 int idx 0; // 队尾指针指向下一个空位 long long totalCost 0; // 总花费注意可能超过int范围 int main() { int n; cin n; for (int k 0; k n; k) { int type, price, t; cin type price t; // 步骤1: 清理过期优惠券无论是否使用 while (i idx t - coupons[i].time 45) { i; } // 确保查找指针j不落后于队首指针i if (j i) { j i; } if (type 0) { // 乘坐地铁 totalCost price; // 获得优惠券加入队尾 coupons[idx].time t; coupons[idx].price price; coupons[idx].used false; idx; } else { // 乘坐公交车 bool found false; // 从j开始查找可用的优惠券 for (int p j; p idx; p) { if (!coupons[p].used coupons[p].price price) { // 找到符合条件的券 coupons[p].used true; found true; // 重要更新j指针到p1因为p之前的券对于后续查找都“无效”了 // 解释p之前的券要么已使用要么面值小于当前price。 // 对于后面票价price的公交这些券更不可能满足条件。 j p 1; break; } } if (!found) { totalCost price; } } } cout totalCost endl; return 0; }代码关键点解析数据结构使用定长数组coupons模拟队列i是头idx是尾新元素插入位置。used标记是否已使用。过期清理(while (i idx t - coupons[i].time 45)): 严格判断大于45分钟因为题目条件是“45”有效所以“45”过期。清理时i已使用的券也会被清理掉这很关键保证了空间和时间的效率。指针j的维护j是查找的起点。if (j i) j i;这行保证了当队首清理后j不会指向一个已经被清理无效的位置。查找与更新j(for (int p j; p idx; p)): 这是双指针优化的核心。查找从j开始。一旦找到符合条件的券除了标记使用和跳出循环我们还将j更新为p1。为什么因为位置p之前的券即下标在[j, p-1]区间的券在这次查找中被扫描过且跳过了。它们被跳过只有两种可能①已使用②未使用但面值 price。对于未来时间更晚的公交车其票价price_future price_current不一定但即使更小这些券也可能因为时间或面值原因无效。更重要的是由于时间递增未来公交车的查找起点j至少是当前的j所以这些被跳过的券永远不会再被考虑。这保证了j只增不减整个查找过程所有p的移动加起来是O(n)的。时间复杂度每个元素入队一次每个元素最多被i和j指针各访问一次清理和查找因此是严格的O(n)完美应对10^5的数据量。数据类型总花费totalCost使用long long因为极端情况下所有行程都付费总花费可能超过int范围10^5 * 1000 10^8仍在int内但习惯上好。5. 常见错误与调试心得这道题在实战中错误率很高以下是我总结的几个常见“坑点”和调试技巧。5.1 错误类型与排查表错误类型可能现象原因分析解决方法理解错误样例不过或得分很低1. 忽略了“选择最早获得”的券随便用一张。2. 错误理解有效期如认为是“获得后45分钟内”而非“乘车前45分钟内获得”。3. 认为优惠券可以累积多次使用。重新精读题目用笔在纸上模拟题目给的样例。超时TLE大数据点全部超时使用了O(n^2)的暴力算法每次公交遍历所有历史券。采用队列维护有效券并尝试双指针优化确保复杂度为O(n)。答案错误WA部分测试点错误1.过期判断条件写错t - coupon.time 45写成。2.指针维护错误j指针在清理过期券后没有与i同步 (if (j i) j i)。3.面值比较错误公交使用券条件是券.price bus.price漏了等号。4.数据类型溢出总花费用了int在极大情况下溢出成负数。1. 仔细核对边界条件。2. 添加打印语句输出关键步骤后i, j, idx的值和队列状态进行人工核对。3. 使用long long存储总花费。运行时错误RE如数组越界数组大小开小了。n最大为100000但优惠券数量最多也可能接近n。将数组大小至少设为100005或更大。5.2 调试与测试技巧构造边界数据全地铁输入全为0检查总花费是否为所有票价之和。全公交输入全为1且票价很高检查是否全部自费。时间边界设计一张券在第45分钟刚好被使用以及在第46分钟过期的情况。面值边界设计一张券面值刚好等于公交车票价的情况。“最早获得”规则验证在有效期内有两张满足面值的券时间分别为t1和t2(t1t2)公交车时间t确保程序选择了t1的券。使用小规模数据打印中间状态这是最有效的调试方法。在清理过期券、查找优惠券、更新指针等关键步骤后打印出当前队列内容、各指针位置、总花费。与手工计算过程对比能快速定位逻辑错误。理解双指针的单调性如果使用双指针优化务必在脑中或纸上模拟i和j的移动。i只随当前时间t增长而右移清理。j只在找到券后向右跳且不会小于i。它们的单调不降是正确性的保证。6. 算法扩展与思维提升解决这道题绝不仅仅是为了AC。它蕴含的算法思想可以迁移到许多其他场景。滑动窗口最大值/最小值问题本题中我们维护了一个45分钟的“时间窗口”并在窗口内查找满足特定条件面值票价的元素。这与经典的滑动窗口问题有相似之处但查找条件更复杂。如果题目变为“求45分钟内最大面值的优惠券”就可以直接用单调队列在O(1)时间内解决。任务调度与资源分配可以把优惠券看作一种“资源”有生效时间和价值把公交车看作“任务”有发生时间和资源需求。问题就变成了如何按时间顺序处理任务并为每个任务分配一个“最早可用且满足条件”的资源。这种模型在操作系统、生产调度中很常见。离线查询与在线处理本题要求在线处理按输入顺序即时决策。如果题目改为先给出所有记录再询问总花费就成了离线问题或许可以用差分、排序等不同方法解决。从模拟到优化这道题是一个经典的范例展示了如何将一个直观的O(n^2)模拟过程通过分析问题性质时间有序、有效期、贪心选择逐步优化到O(n)。这种“先实现朴素算法再寻找优化点”的思维模式是解决所有算法竞赛题目的通用法门。最后我的个人体会是像“公交换乘”这类模拟题是锻炼编程严谨性和算法优化思维的绝佳材料。它要求你像机器一样精确理解规则又要求你像数学家一样抽象出模型并优化。多练习这类题目当你再看到诸如“预约系统”、“订单处理”、“日志分析”等实际问题时你会自然而然地想到队列、滑动窗口、双指针这些工具思考如何设计高效的数据流转方案。这才是信息学竞赛带给我们的超越比赛本身的长期价值。