第一次看到《不开心的小朋友》这个题目时我以为是道脑筋急转弯想考什么心理学的“情绪管理”。点进去一看好家伙是一道 200 分的模拟大题名字还挺有迷惑性。真正做起来才发现题目本身不复杂复杂的是数据规模一大朴素模拟直接超时必须用合适的数据结构去优化。当时我用了 Java、JS、Python 三个版本分别实现踩了不少坑这里把完整思路和实现细节整理出来给同样在备考或刷题的朋友做个参考。这道题的核心场景是若干个小朋友按轮次到达游乐设施排队每人有一个耐心值如果等待时间超过耐心值就会“不开心”并离开。你需要模拟完整过程统计能玩到设施的小朋友数量、游玩顺序以及不开心离开的人数。题名虽然轻松但涉及优先队列、延迟删除、多语言适配是一道非常典型的“看着难、想通后考基本功”的题目。1. 题意还原先搞清楚“不开心”的判定规则1.1 从标题能读出的关键信息“新卷”说明这是近期加入题库的题目“200分”代表它在整套试卷里属于高分大题“Java JS Python”则暗示这套题需要候选人在三种语言中任选一种实现。这类题目通常不会让你简单地用数组一趟趟扫完而是会在数据范围上做文章逼着你用更高效的方式做模拟。“不开心的小朋友”这个题目名称很有误导性。第一次看我以为是求某种情绪状态最大值或者是 DP 题目。实际接触后它就是一个带超时机制的排队叫号模拟设施每轮能接待固定数量的小朋友小朋友从到达开始排队等得太久就会生气走人。你要做的就是把整个过程按规则推演完输出最终结果。1.2 规则细节与输入输出约定题目的模拟规则可以统一描述成这样有一个游乐设施每轮最多同时接待 M 个小朋友。有 N 个小朋友编号从 1 到 N每个小朋友有一个到达轮次 a_i 和一个耐心值 t_i。第 k 轮开始时先让所有 a_i k 的小朋友进入等待区。然后检查等待区中所有小朋友如果当前轮次 k 减到达轮次 a_i 大于耐心值 t_i也就是 k - a_i t_i该小朋友就会不开心并离开队伍。接着从剩余等待的小朋友中选择最多 M 个人上设施游玩。游玩顺序有优先级等待时间更长的小朋友优先如果等待时间相同则编号更小的优先。总共模拟 T 轮结束后需要统计开心人数、开心小朋友的编号顺序以及不开心离开的人数。这里最容易出问题的是超时判定。题目说的是“超过耐心值”不是“达到耐心值”。也就是说如果某个小朋友第 2 轮到达耐心值 0那么他在第 3 轮开始时已经等了 1 轮1 0超时离开但他在第 2 轮刚到达时等待 0 轮0 0 不成立所以不会立刻离开。很多人在这个边界上栽过跟头。输入输出格式通常是这样第一行N M T 接下来 N 行a_i t_i输出三行第一行开心的小朋友数量 第二行开心的小朋友编号按实际游玩顺序输出空格分隔 第三行不开心离开的小朋友数量1.3 一个手算样例把规则跑一遍拿一个能覆盖超时和正常游玩两种情况的样例来说5 1 4 1 1 1 3 2 0 3 1 3 0这里 N5M1T4设施每轮只能接待 1 个小朋友。逐轮模拟轮次本轮到达超时检查本轮游玩离开11号、2号无1号无23号无2号无34号、5号3号超时离开4号3号4无5号超时离开无5号第 1 轮1号和2号到达没人超时设施选等待时间最长的人两人都是第 1 轮到达编号小的 1号先玩。第 2 轮3号到达等待区里有 2号和3号。2号等待了 1 轮耐心值 3没超时3号刚来等待 0 轮耐心值 0没超时。选人时2号到达轮更早优先游玩。第 3 轮4号、5号到达。3号已经在等待区里等了一轮耐心值是 01 大于 0超时离开。剩下的等待者是4号、5号同轮到达编号小的4号游玩。第 4 轮5号等了一轮耐心值 0超时离开。最终开心的小朋友是 1号、2号、4号共 3 个不开心的是 3号、5号共 2 个。输出 3 1 2 4 2这个样例虽然简单但覆盖了“临界轮次”的两种情况3号在第 3 轮超时5号在第 4 轮超时说明超时判定不是统一的等待轮数而是由各自的耐心值决定。2. 从朴素模拟到双堆解法两个优先队列如何分工2.1 朴素模拟为什么会被卡看到题目第一眼很多人会想直接用一个数组或者 ArrayList 维护等待区每一轮遍历一遍判断哪些人超时然后排序选前 M 个人。这个思路对于小数据没有问题但一旦 N 和 T 都到 10^5 级别每轮都遍历整个等待区复杂度最坏会到 O(N*T)也就是 10^10 次操作必然超时。我一开始也写了这个朴素版本样例秒过提交后直接超时。这时候才意识到这道题真正的考点不是“会不会模拟”而是“能不能高效模拟”。等待区的变化看似简单实际上每一轮都要做两类操作超时删除和按顺序选人。两类操作都要求从集合中快速取出符合条件的元素只是条件不同。2.2 临界轮公式把超时判断变成可比较的键先来看超时判断。一个人在第 k 轮开始时是否超时用原始条件判断是k - a_i t_i移项一下就得到k a_i t_i换句话说每个小朋友都有一个“超时临界轮次”deadline a_i t_i 1当当前轮次 k 等于这个 deadline 时他就已经超时了。比如刚才样例里的 3号a2t0deadline3所以第 3 轮开头就离开。5号a3t0deadline4所以第 4 轮离开。这个公式看起来只是移了个项但它把“每轮扫描判断”变成了“提前算好一个值然后按值从小到大处理”。只要维护一个最小堆按 deadline 排序每轮开始就把堆顶 deadline 等于当前轮的人全部弹出就能做到均摊 O(1) 地找到所有超时者。这是整个优化的第一块基石。2.3 为什么一个堆不够既然超时可以用堆处理那选人能不能也用一个堆问题在于超时优先的排序标准和游玩优先的排序标准不一样。超时检查要按 deadline 从小到大取人因为 deadline 小的人更紧迫可能马上要走人。但游玩顺序要求“等待时间更长的人优先”也就是到达轮次 a_i 更小的人优先。一个人可能到达得很早、等待时间很长但他的耐心值很大deadline 很晚另一个人可能刚到没多久但耐心值很小deadline 很近。如果只用超时堆来选玩就会优先把刚到的耐心小的人叫走这不符合题意的游玩顺序。反过来如果只用到达顺序堆来选人又无法快速找出已经超时的人因为等待区的队头没有超时不代表队列中间或后面没有人超时。比如样例中的 3号他在第 3 轮超时时队列顺序是 3号、4号、5号队头 3号确实超时了可以直接弹掉但如果换一种样例队头到达早但耐心大队尾到达晚但耐心为 0队尾的超时就无法通过简单的队头弹出解决。所以标准解法需要两个数据结构一个按 (a_i, 编号) 排序负责选出本轮游玩的人另一个按 deadline 排序负责快速找出超时离开的人。两者维护同一个等待集合只是视角不同。2.4 双向延迟删除双堆方案最关键的细节用两个结构维护同一批人必然遇到一个问题某个人在 A 结构里被删除了但 B 结构里还有他的记录反之亦然。具体到这道题如果某个人从游玩堆里被弹出说明他已经玩到了但他的记录还留在超时堆里。后续超时堆弹出他的记录时必须跳过。如果某个人从超时堆里被弹出说明他已经离开但他的记录还留在游玩堆里。后续游玩堆弹出他的记录时也必须跳过。这就是“双向延迟删除”。实现方式不是真的去另一个结构里删除元素而是给每个人维护两个布尔状态played 表示是否已经玩到gone 表示是否已经超时离开。每次从堆里弹出一条记录时先检查这两个状态如果已经玩过或已经离开直接丢弃否则才进行相应的业务处理。我当时刚想到双堆方案时觉得挺完美的直到写完代码才发现延迟删除才是最容易写错的地方。漏掉任何一个方向的跳过判断都会导致把已经走的人拉回来玩或者把已经玩过的人重复统计。3. Java实现TreeSet与优先队列的协同细节3.1 数据结构选型Java 版本里我选择了 TreeSet 来维护等待队伍因为 Java 原生提供了有序集合可以按照自定义顺序快速取出最小值也就是游玩优先级最高的那个人。TreeSet 内部是红黑树pollFirst 和 remove 都是 O(log N) 的操作完全符合需求。超时堆则用 PriorityQueue元素是一个 long 数组或者自定义对象按 deadline、到达轮、编号依次排序。这里有一个小技巧等待队伍里的每个元素可以用一个 long 值来表示高 32 位是到达轮次低 32 位是编号。这样一个值就能同时满足 TreeSet 的比较需求省得写一个冗长的 Comparator。之所以用 long 而不是字符串或数组是因为 long 值可以直接做大小比较占用空间小排序快。后续从 key 里还原编号时把低 32 位取出来即可。3.2 核心代码import java.util.*; public class UnhappyKids { private static long encodeKey(int arrive, int id) { return ((long) arrive 32) | (id 0xffffffffL); } public static void main(String[] args) { Scanner sc new Scanner(System.in); int N sc.nextInt(); int M sc.nextInt(); int T sc.nextInt(); ListListInteger arrivals new ArrayList(); for (int i 0; i T; i) { arrivals.add(new ArrayList()); } int[] a new int[N 1]; int[] t new int[N 1]; for (int i 1; i N; i) { a[i] sc.nextInt(); t[i] sc.nextInt(); arrivals.get(a[i]).add(i); } TreeSetLong waiting new TreeSet(); PriorityQueuelong[] timeoutHeap new PriorityQueue((x, y) - { if (x[0] ! y[0]) return Long.compare(x[0], y[0]); if (x[1] ! y[1]) return Long.compare(x[1], y[1]); return Long.compare(x[2], y[2]); }); boolean[] played new boolean[N 1]; boolean[] gone new boolean[N 1]; ListInteger order new ArrayList(); int unhappy 0; for (int k 1; k T; k) { for (int id : arrivals.get(k)) { long deadline (long) a[id] t[id] 1; waiting.add(encodeKey(a[id], id)); timeoutHeap.offer(new long[]{deadline, a[id], id}); } while (!timeoutHeap.isEmpty() timeoutHeap.peek()[0] k) { long[] top timeoutHeap.poll(); int id (int) top[2]; if (played[id] || gone[id]) continue; gone[id] true; unhappy; waiting.remove(encodeKey(a[id], id)); } int cnt 0; while (cnt M !waiting.isEmpty()) { long key waiting.pollFirst(); int id (int) (key 0xffffffffL); played[id] true; order.add(id); cnt; } } System.out.println(order.size()); for (int i 0; i order.size(); i) { if (i 0) System.out.print( ); System.out.print(order.get(i)); } System.out.println(); System.out.println(unhappy); } }3.3 几个容易踩的坑第一long key 的还原。我一开始直接用(int) key去拿编号结果发现负数。因为高 32 位是到达轮强转 int 会把整个 long 变成 int编号位置也乱了。正确做法是key 0xffffffffL只取低 32 位无符号值。第二超时处理的比较条件。入堆时 deadline 是a[i] t[i] 1清理时用 k而不是 k。虽然正常情况下不会出现 deadline 小于当前轮次的脏数据但写成更稳妥能防止某些边界条件把历史残留数据一起处理掉。第三TreeSet 的 remove 必须使用和 add 时相同的 key。因为同一个 id 的 a 值是固定的所以重新构造 key 可以正常删除。如果你在循环里用自定义对象存储忘了重写 equals 和 hashCoderemove 就会失效这是 Java 用户最容易犯的错。4. JavaScript实现手写堆完成同样的模拟4.1 为什么需要手写堆JavaScript 没有内置的 PriorityQueue和 Java 的 TreeSet 更是完全不沾边。所以在 JS 版里必须自己实现最小堆。这个过程不复杂但要注意比较函数的设计因为同一个堆可能在不同场景下排序规则不同。我建议把最小堆封装成一个类构造函数接收一个比较函数。这样可以用一套堆模板同时扮演“游玩堆”和“超时堆”只是传入的比较规则不同。刷题时这个模板可以反复用属于性价比很高的投入。JS 版本的双向延迟删除比 Java 更对称Java 里游玩侧用 TreeSet 直接物理删除了元素超时侧用堆加延迟删除而 JS 里两个堆都是逻辑删除两边都靠状态数组跳过所以更能体现“双堆延迟删除”这一整套思想。4.2 核心代码class MinHeap { constructor(cmp) { this.heap []; this.cmp cmp; } size() { return this.heap.length; } isEmpty() { return this.heap.length 0; } peek() { return this.heap[0]; } push(item) { this.heap.push(item); this._up(this.heap.length - 1); } pop() { if (this.heap.length 0) return null; const top this.heap[0]; const last this.heap.pop(); if (this.heap.length 0) { this.heap[0] last; this._down(0); } return top; } _up(idx) { while (idx 0) { const parent (idx - 1) 1; if (this.cmp(this.heap[idx], this.heap[parent]) 0) { [this.heap[idx], this.heap[parent]] [this.heap[parent], this.heap[idx]]; idx parent; } else { break; } } } _down(idx) { const n this.heap.length; while (true) { let left idx * 2 1; let right idx * 2 2; let smallest idx; if (left n this.cmp(this.heap[left], this.heap[smallest]) 0) smallest left; if (right n this.cmp(this.heap[right], this.heap[smallest]) 0) smallest right; if (smallest idx) break; [this.heap[idx], this.heap[smallest]] [this.heap[smallest], this.heap[idx]]; idx smallest; } } } const fs require(fs); const input fs.readFileSync(0, utf8).trim().split(/\s/); let ptr 0; const N Number(input[ptr]); const M Number(input[ptr]); const T Number(input[ptr]); const arrivals Array.from({ length: T 1 }, () []); const a new Array(N 1).fill(0); const t new Array(N 1).fill(0); for (let i 1; i N; i) { a[i] Number(input[ptr]); t[i] Number(input[ptr]); arrivals[a[i]].push(i); } const playHeap new MinHeap((x, y) { if (x[0] ! y[0]) return x[0] - y[0]; return x[1] - y[1]; }); const timeoutHeap new MinHeap((x, y) { if (x[0] ! y[0]) return x[0] - y[0]; if (x[1] ! y[1]) return x[1] - y[1]; return x[2] - y[2]; }); const played new Array(N 1).fill(false); const gone new Array(N 1).fill(false); const order []; let unhappy 0; for (let k 1; k T; k) { for (const id of arrivals[k]) { playHeap.push([a[id], id]); timeoutHeap.push([a[id] t[id] 1, a[id], id]); } while (!timeoutHeap.isEmpty() timeoutHeap.peek()[0] k) { const top timeoutHeap.pop(); const id top[2]; if (played[id] || gone[id]) continue; gone[id] true; unhappy; } let cnt 0; while (cnt M !playHeap.isEmpty()) { const top playHeap.pop(); const id top[1]; if (played[id] || gone[id]) continue; played[id] true; order.push(id); cnt; } } console.log(order.length); console.log(order.join( )); console.log(unhappy);4.3 性能与内存注意点JS 版本的性能瓶颈一般不在堆操作而在数组扩容和 toString 拼接。数据规模到 10^5 时直接用字符串拼接输出编号列表即可不要用每次拼一个又长又大的字符串会有性能损耗。我这里用order.join( )是最稳妥的方式。另一个注意点是 Heap 里存的是数组频繁创建数组会有内存分配开销。但在 10^5 级别完全够用不需要刻意用对象池优化。手写堆时把_up和_down写熟练避免递归递归容易爆栈。5. Python实现heapq版本与三语言对比5.1 heapq 的快速实现Python 版本的思路一致但实现更简洁因为heapq和元组的天然比较让代码量少了很多。playHeap 中直接存(到达轮, 编号)timeoutHeap 中直接存(临界轮, 到达轮, 编号)Python 元组会按顺序自动比较。import sys import heapq def solve(): data list(map(int, sys.stdin.buffer.read().split())) it iter(data) N next(it) M next(it) T next(it) arrivals [[] for _ in range(T 1)] a [0] * (N 1) t [0] * (N 1) for i in range(1, N 1): ai next(it) ti next(it) a[i] ai t[i] ti arrivals[ai].append(i) play_heap [] timeout_heap [] played [False] * (N 1) gone [False] * (N 1) order [] unhappy 0 for k in range(1, T 1): for pid in arrivals[k]: heapq.heappush(play_heap, (a[pid], pid)) heapq.heappush(timeout_heap, (a[pid] t[pid] 1, a[pid], pid)) while timeout_heap and timeout_heap[0][0] k: _, _, pid heapq.heappop(timeout_heap) if played[pid] or gone[pid]: continue gone[pid] True unhappy 1 cnt 0 while cnt M and play_heap: _, pid heapq.heappop(play_heap) if played[pid] or gone[pid]: continue played[pid] True order.append(pid) cnt 1 sys.stdout.write(str(len(order)) \n) sys.stdout.write( .join(map(str, order)) \n) sys.stdout.write(str(unhappy) \n) if __name__ __main__: solve()5.2 三语言实现对比对比项JavaJavaScriptPython等待队列数据结构TreeSet手写最小堆heapq超时队列数据结构PriorityQueue手写最小堆heapq选玩顺序维护TreeSet 内建排序自定义比较函数元组天然比较超时顺序维护Comparator 三个字段自定义比较函数元组天然比较删除方式游玩侧物理删除超时侧延迟删除双延迟删除双延迟删除代码量中等偏多最少主要易错点key 还原、TreeSet remove手写堆比较函数输入解析类型从代码量看Python 最少因为元组比较和 heapq 直接解决了大部分问题。Java 最直观TreeSet 的 pollFirst 让游玩侧逻辑非常清晰。JS 则折中但手写堆模板有一定代码成本。5.3 机考中三语言怎么选如果目标是快速 AC且数据范围不大我会优先选 Python代码最短心智负担最小。但有些机考环境对 Python 执行时间卡得比较严或者 Python 版本较旧此时 Java 的 TreeSet 方案会更稳因为红黑树操作稳定不依赖解释器优化。如果只熟悉 JavaScript也不要慌堆模板背熟之后这道题完全能写。唯一要注意的是输入解析和输出格式Node.js 环境用fs.readFileSync(0, utf8)读取标准输入是最稳的做法。还有一点JS 的 Number 是双精度浮点但 10^5 级别的整数运算完全不会出现精度问题不需要用 BigInt。6. 题目背后的三类扩展与做题策略6.1 把“先到先玩”改成“让不开心人数最少”有些变体不会明确告诉你游玩顺序而是让你自己决定每轮让谁玩目标是让不开心的人数尽量少。这个版本就需要一点贪心思维每轮设施有空位时应该优先让“最容易超时”的人玩也就是 deadline 最小的人。因为你每拖一轮他就更接近超时临界点。实现上反而比原题更简单因为你只需要一个超时堆每轮从堆顶弹出 deadline 小于等于当前轮的人代表超时放弃然后再从堆顶选 deadline 最小的人去玩。这样能保证每个时间点都在尽可能抢救最紧迫的小朋友。这种变体我在别的题库里也见过核心模型几乎一样只是游玩排序规则不同。6.2 把“每轮固定 M 人”改成“每轮人数可调整”如果题目允许每轮根据排队人数动态决定接待多少个小朋友或者设施在不同轮次能力不同问题就变成了一个资源分配模型可能需要动态规划配合贪心。这种扩展已经把题目的难度抬高了一个层次通常不会出现在同一张试卷上但如果你遇到需要跳出“模拟”的框架去想。我的建议是刷题时先看数据范围。N、T 都小暴力模拟足够N、T 都在 10^5 左右双堆方案就是标准解如果还有额外的资源维度再考虑叠加其他数据结构。数据范围是选题思路的第一依据不要一上来就想复杂解法。6.3 刷这类题我推荐的三步走第一步手算样例。不要急着写代码先把题目给的样例在纸上跑一遍搞清楚超时判定发生在选人之前还是之后游玩顺序按什么排。这些规则一旦理解错后面的代码全白写。第二步朴素实现打底。即使你知道有优化方案也可以先写一个 O(N*T) 的版本用样例验证自己对题意的理解是否正确。我在做这道题时朴素版虽然提交超时但至少保证了逻辑上的正确性后续优化时可以用它来对拍。第三步对拍验证。优化版写完以后用随机小数据把两个版本的结果反复对比。我当时专门写了一个小脚本随机生成 N 和 T 都在 20 以内、M 在 5 以内的数据跑了上千组确认双堆版本的输出和朴素版本完全一致才敢提交。延迟删除这种逻辑靠肉眼检查很难发现漏判对拍是最可靠的验证方式。这道题做完我最大的收获不是记住了双堆解法而是理解了“双堆延迟删除”这套组合背后的适用条件当一个集合需要同时以两种不同维度做优先级操作时不要试图用一个结构硬存两个结构各自维护一种优先级再用状态数组兜底才是清晰的解法。以后遇到类似题目哪怕结构不同这套思路也能直接迁移。最后一个小建议任何涉及“逻辑删除”的模拟题状态数组一定要在每次弹出后、业务操作前检查顺序错一点输出就全错了。
第一次看到《不开心的小朋友》这个题目时我以为是道脑筋急转弯想考什么心理学的“情绪管理”。点进去一看好家伙是一道 200 分的模拟大题名字还挺有迷惑性。真正做起来才发现题目本身不复杂复杂的是数据规模一大朴素模拟直接超时必须用合适的数据结构去优化。当时我用了 Java、JS、Python 三个版本分别实现踩了不少坑这里把完整思路和实现细节整理出来给同样在备考或刷题的朋友做个参考。这道题的核心场景是若干个小朋友按轮次到达游乐设施排队每人有一个耐心值如果等待时间超过耐心值就会“不开心”并离开。你需要模拟完整过程统计能玩到设施的小朋友数量、游玩顺序以及不开心离开的人数。题名虽然轻松但涉及优先队列、延迟删除、多语言适配是一道非常典型的“看着难、想通后考基本功”的题目。1. 题意还原先搞清楚“不开心”的判定规则1.1 从标题能读出的关键信息“新卷”说明这是近期加入题库的题目“200分”代表它在整套试卷里属于高分大题“Java JS Python”则暗示这套题需要候选人在三种语言中任选一种实现。这类题目通常不会让你简单地用数组一趟趟扫完而是会在数据范围上做文章逼着你用更高效的方式做模拟。“不开心的小朋友”这个题目名称很有误导性。第一次看我以为是求某种情绪状态最大值或者是 DP 题目。实际接触后它就是一个带超时机制的排队叫号模拟设施每轮能接待固定数量的小朋友小朋友从到达开始排队等得太久就会生气走人。你要做的就是把整个过程按规则推演完输出最终结果。1.2 规则细节与输入输出约定题目的模拟规则可以统一描述成这样有一个游乐设施每轮最多同时接待 M 个小朋友。有 N 个小朋友编号从 1 到 N每个小朋友有一个到达轮次 a_i 和一个耐心值 t_i。第 k 轮开始时先让所有 a_i k 的小朋友进入等待区。然后检查等待区中所有小朋友如果当前轮次 k 减到达轮次 a_i 大于耐心值 t_i也就是 k - a_i t_i该小朋友就会不开心并离开队伍。接着从剩余等待的小朋友中选择最多 M 个人上设施游玩。游玩顺序有优先级等待时间更长的小朋友优先如果等待时间相同则编号更小的优先。总共模拟 T 轮结束后需要统计开心人数、开心小朋友的编号顺序以及不开心离开的人数。这里最容易出问题的是超时判定。题目说的是“超过耐心值”不是“达到耐心值”。也就是说如果某个小朋友第 2 轮到达耐心值 0那么他在第 3 轮开始时已经等了 1 轮1 0超时离开但他在第 2 轮刚到达时等待 0 轮0 0 不成立所以不会立刻离开。很多人在这个边界上栽过跟头。输入输出格式通常是这样第一行N M T 接下来 N 行a_i t_i输出三行第一行开心的小朋友数量 第二行开心的小朋友编号按实际游玩顺序输出空格分隔 第三行不开心离开的小朋友数量1.3 一个手算样例把规则跑一遍拿一个能覆盖超时和正常游玩两种情况的样例来说5 1 4 1 1 1 3 2 0 3 1 3 0这里 N5M1T4设施每轮只能接待 1 个小朋友。逐轮模拟轮次本轮到达超时检查本轮游玩离开11号、2号无1号无23号无2号无34号、5号3号超时离开4号3号4无5号超时离开无5号第 1 轮1号和2号到达没人超时设施选等待时间最长的人两人都是第 1 轮到达编号小的 1号先玩。第 2 轮3号到达等待区里有 2号和3号。2号等待了 1 轮耐心值 3没超时3号刚来等待 0 轮耐心值 0没超时。选人时2号到达轮更早优先游玩。第 3 轮4号、5号到达。3号已经在等待区里等了一轮耐心值是 01 大于 0超时离开。剩下的等待者是4号、5号同轮到达编号小的4号游玩。第 4 轮5号等了一轮耐心值 0超时离开。最终开心的小朋友是 1号、2号、4号共 3 个不开心的是 3号、5号共 2 个。输出 3 1 2 4 2这个样例虽然简单但覆盖了“临界轮次”的两种情况3号在第 3 轮超时5号在第 4 轮超时说明超时判定不是统一的等待轮数而是由各自的耐心值决定。2. 从朴素模拟到双堆解法两个优先队列如何分工2.1 朴素模拟为什么会被卡看到题目第一眼很多人会想直接用一个数组或者 ArrayList 维护等待区每一轮遍历一遍判断哪些人超时然后排序选前 M 个人。这个思路对于小数据没有问题但一旦 N 和 T 都到 10^5 级别每轮都遍历整个等待区复杂度最坏会到 O(N*T)也就是 10^10 次操作必然超时。我一开始也写了这个朴素版本样例秒过提交后直接超时。这时候才意识到这道题真正的考点不是“会不会模拟”而是“能不能高效模拟”。等待区的变化看似简单实际上每一轮都要做两类操作超时删除和按顺序选人。两类操作都要求从集合中快速取出符合条件的元素只是条件不同。2.2 临界轮公式把超时判断变成可比较的键先来看超时判断。一个人在第 k 轮开始时是否超时用原始条件判断是k - a_i t_i移项一下就得到k a_i t_i换句话说每个小朋友都有一个“超时临界轮次”deadline a_i t_i 1当当前轮次 k 等于这个 deadline 时他就已经超时了。比如刚才样例里的 3号a2t0deadline3所以第 3 轮开头就离开。5号a3t0deadline4所以第 4 轮离开。这个公式看起来只是移了个项但它把“每轮扫描判断”变成了“提前算好一个值然后按值从小到大处理”。只要维护一个最小堆按 deadline 排序每轮开始就把堆顶 deadline 等于当前轮的人全部弹出就能做到均摊 O(1) 地找到所有超时者。这是整个优化的第一块基石。2.3 为什么一个堆不够既然超时可以用堆处理那选人能不能也用一个堆问题在于超时优先的排序标准和游玩优先的排序标准不一样。超时检查要按 deadline 从小到大取人因为 deadline 小的人更紧迫可能马上要走人。但游玩顺序要求“等待时间更长的人优先”也就是到达轮次 a_i 更小的人优先。一个人可能到达得很早、等待时间很长但他的耐心值很大deadline 很晚另一个人可能刚到没多久但耐心值很小deadline 很近。如果只用超时堆来选玩就会优先把刚到的耐心小的人叫走这不符合题意的游玩顺序。反过来如果只用到达顺序堆来选人又无法快速找出已经超时的人因为等待区的队头没有超时不代表队列中间或后面没有人超时。比如样例中的 3号他在第 3 轮超时时队列顺序是 3号、4号、5号队头 3号确实超时了可以直接弹掉但如果换一种样例队头到达早但耐心大队尾到达晚但耐心为 0队尾的超时就无法通过简单的队头弹出解决。所以标准解法需要两个数据结构一个按 (a_i, 编号) 排序负责选出本轮游玩的人另一个按 deadline 排序负责快速找出超时离开的人。两者维护同一个等待集合只是视角不同。2.4 双向延迟删除双堆方案最关键的细节用两个结构维护同一批人必然遇到一个问题某个人在 A 结构里被删除了但 B 结构里还有他的记录反之亦然。具体到这道题如果某个人从游玩堆里被弹出说明他已经玩到了但他的记录还留在超时堆里。后续超时堆弹出他的记录时必须跳过。如果某个人从超时堆里被弹出说明他已经离开但他的记录还留在游玩堆里。后续游玩堆弹出他的记录时也必须跳过。这就是“双向延迟删除”。实现方式不是真的去另一个结构里删除元素而是给每个人维护两个布尔状态played 表示是否已经玩到gone 表示是否已经超时离开。每次从堆里弹出一条记录时先检查这两个状态如果已经玩过或已经离开直接丢弃否则才进行相应的业务处理。我当时刚想到双堆方案时觉得挺完美的直到写完代码才发现延迟删除才是最容易写错的地方。漏掉任何一个方向的跳过判断都会导致把已经走的人拉回来玩或者把已经玩过的人重复统计。3. Java实现TreeSet与优先队列的协同细节3.1 数据结构选型Java 版本里我选择了 TreeSet 来维护等待队伍因为 Java 原生提供了有序集合可以按照自定义顺序快速取出最小值也就是游玩优先级最高的那个人。TreeSet 内部是红黑树pollFirst 和 remove 都是 O(log N) 的操作完全符合需求。超时堆则用 PriorityQueue元素是一个 long 数组或者自定义对象按 deadline、到达轮、编号依次排序。这里有一个小技巧等待队伍里的每个元素可以用一个 long 值来表示高 32 位是到达轮次低 32 位是编号。这样一个值就能同时满足 TreeSet 的比较需求省得写一个冗长的 Comparator。之所以用 long 而不是字符串或数组是因为 long 值可以直接做大小比较占用空间小排序快。后续从 key 里还原编号时把低 32 位取出来即可。3.2 核心代码import java.util.*; public class UnhappyKids { private static long encodeKey(int arrive, int id) { return ((long) arrive 32) | (id 0xffffffffL); } public static void main(String[] args) { Scanner sc new Scanner(System.in); int N sc.nextInt(); int M sc.nextInt(); int T sc.nextInt(); ListListInteger arrivals new ArrayList(); for (int i 0; i T; i) { arrivals.add(new ArrayList()); } int[] a new int[N 1]; int[] t new int[N 1]; for (int i 1; i N; i) { a[i] sc.nextInt(); t[i] sc.nextInt(); arrivals.get(a[i]).add(i); } TreeSetLong waiting new TreeSet(); PriorityQueuelong[] timeoutHeap new PriorityQueue((x, y) - { if (x[0] ! y[0]) return Long.compare(x[0], y[0]); if (x[1] ! y[1]) return Long.compare(x[1], y[1]); return Long.compare(x[2], y[2]); }); boolean[] played new boolean[N 1]; boolean[] gone new boolean[N 1]; ListInteger order new ArrayList(); int unhappy 0; for (int k 1; k T; k) { for (int id : arrivals.get(k)) { long deadline (long) a[id] t[id] 1; waiting.add(encodeKey(a[id], id)); timeoutHeap.offer(new long[]{deadline, a[id], id}); } while (!timeoutHeap.isEmpty() timeoutHeap.peek()[0] k) { long[] top timeoutHeap.poll(); int id (int) top[2]; if (played[id] || gone[id]) continue; gone[id] true; unhappy; waiting.remove(encodeKey(a[id], id)); } int cnt 0; while (cnt M !waiting.isEmpty()) { long key waiting.pollFirst(); int id (int) (key 0xffffffffL); played[id] true; order.add(id); cnt; } } System.out.println(order.size()); for (int i 0; i order.size(); i) { if (i 0) System.out.print( ); System.out.print(order.get(i)); } System.out.println(); System.out.println(unhappy); } }3.3 几个容易踩的坑第一long key 的还原。我一开始直接用(int) key去拿编号结果发现负数。因为高 32 位是到达轮强转 int 会把整个 long 变成 int编号位置也乱了。正确做法是key 0xffffffffL只取低 32 位无符号值。第二超时处理的比较条件。入堆时 deadline 是a[i] t[i] 1清理时用 k而不是 k。虽然正常情况下不会出现 deadline 小于当前轮次的脏数据但写成更稳妥能防止某些边界条件把历史残留数据一起处理掉。第三TreeSet 的 remove 必须使用和 add 时相同的 key。因为同一个 id 的 a 值是固定的所以重新构造 key 可以正常删除。如果你在循环里用自定义对象存储忘了重写 equals 和 hashCoderemove 就会失效这是 Java 用户最容易犯的错。4. JavaScript实现手写堆完成同样的模拟4.1 为什么需要手写堆JavaScript 没有内置的 PriorityQueue和 Java 的 TreeSet 更是完全不沾边。所以在 JS 版里必须自己实现最小堆。这个过程不复杂但要注意比较函数的设计因为同一个堆可能在不同场景下排序规则不同。我建议把最小堆封装成一个类构造函数接收一个比较函数。这样可以用一套堆模板同时扮演“游玩堆”和“超时堆”只是传入的比较规则不同。刷题时这个模板可以反复用属于性价比很高的投入。JS 版本的双向延迟删除比 Java 更对称Java 里游玩侧用 TreeSet 直接物理删除了元素超时侧用堆加延迟删除而 JS 里两个堆都是逻辑删除两边都靠状态数组跳过所以更能体现“双堆延迟删除”这一整套思想。4.2 核心代码class MinHeap { constructor(cmp) { this.heap []; this.cmp cmp; } size() { return this.heap.length; } isEmpty() { return this.heap.length 0; } peek() { return this.heap[0]; } push(item) { this.heap.push(item); this._up(this.heap.length - 1); } pop() { if (this.heap.length 0) return null; const top this.heap[0]; const last this.heap.pop(); if (this.heap.length 0) { this.heap[0] last; this._down(0); } return top; } _up(idx) { while (idx 0) { const parent (idx - 1) 1; if (this.cmp(this.heap[idx], this.heap[parent]) 0) { [this.heap[idx], this.heap[parent]] [this.heap[parent], this.heap[idx]]; idx parent; } else { break; } } } _down(idx) { const n this.heap.length; while (true) { let left idx * 2 1; let right idx * 2 2; let smallest idx; if (left n this.cmp(this.heap[left], this.heap[smallest]) 0) smallest left; if (right n this.cmp(this.heap[right], this.heap[smallest]) 0) smallest right; if (smallest idx) break; [this.heap[idx], this.heap[smallest]] [this.heap[smallest], this.heap[idx]]; idx smallest; } } } const fs require(fs); const input fs.readFileSync(0, utf8).trim().split(/\s/); let ptr 0; const N Number(input[ptr]); const M Number(input[ptr]); const T Number(input[ptr]); const arrivals Array.from({ length: T 1 }, () []); const a new Array(N 1).fill(0); const t new Array(N 1).fill(0); for (let i 1; i N; i) { a[i] Number(input[ptr]); t[i] Number(input[ptr]); arrivals[a[i]].push(i); } const playHeap new MinHeap((x, y) { if (x[0] ! y[0]) return x[0] - y[0]; return x[1] - y[1]; }); const timeoutHeap new MinHeap((x, y) { if (x[0] ! y[0]) return x[0] - y[0]; if (x[1] ! y[1]) return x[1] - y[1]; return x[2] - y[2]; }); const played new Array(N 1).fill(false); const gone new Array(N 1).fill(false); const order []; let unhappy 0; for (let k 1; k T; k) { for (const id of arrivals[k]) { playHeap.push([a[id], id]); timeoutHeap.push([a[id] t[id] 1, a[id], id]); } while (!timeoutHeap.isEmpty() timeoutHeap.peek()[0] k) { const top timeoutHeap.pop(); const id top[2]; if (played[id] || gone[id]) continue; gone[id] true; unhappy; } let cnt 0; while (cnt M !playHeap.isEmpty()) { const top playHeap.pop(); const id top[1]; if (played[id] || gone[id]) continue; played[id] true; order.push(id); cnt; } } console.log(order.length); console.log(order.join( )); console.log(unhappy);4.3 性能与内存注意点JS 版本的性能瓶颈一般不在堆操作而在数组扩容和 toString 拼接。数据规模到 10^5 时直接用字符串拼接输出编号列表即可不要用每次拼一个又长又大的字符串会有性能损耗。我这里用order.join( )是最稳妥的方式。另一个注意点是 Heap 里存的是数组频繁创建数组会有内存分配开销。但在 10^5 级别完全够用不需要刻意用对象池优化。手写堆时把_up和_down写熟练避免递归递归容易爆栈。5. Python实现heapq版本与三语言对比5.1 heapq 的快速实现Python 版本的思路一致但实现更简洁因为heapq和元组的天然比较让代码量少了很多。playHeap 中直接存(到达轮, 编号)timeoutHeap 中直接存(临界轮, 到达轮, 编号)Python 元组会按顺序自动比较。import sys import heapq def solve(): data list(map(int, sys.stdin.buffer.read().split())) it iter(data) N next(it) M next(it) T next(it) arrivals [[] for _ in range(T 1)] a [0] * (N 1) t [0] * (N 1) for i in range(1, N 1): ai next(it) ti next(it) a[i] ai t[i] ti arrivals[ai].append(i) play_heap [] timeout_heap [] played [False] * (N 1) gone [False] * (N 1) order [] unhappy 0 for k in range(1, T 1): for pid in arrivals[k]: heapq.heappush(play_heap, (a[pid], pid)) heapq.heappush(timeout_heap, (a[pid] t[pid] 1, a[pid], pid)) while timeout_heap and timeout_heap[0][0] k: _, _, pid heapq.heappop(timeout_heap) if played[pid] or gone[pid]: continue gone[pid] True unhappy 1 cnt 0 while cnt M and play_heap: _, pid heapq.heappop(play_heap) if played[pid] or gone[pid]: continue played[pid] True order.append(pid) cnt 1 sys.stdout.write(str(len(order)) \n) sys.stdout.write( .join(map(str, order)) \n) sys.stdout.write(str(unhappy) \n) if __name__ __main__: solve()5.2 三语言实现对比对比项JavaJavaScriptPython等待队列数据结构TreeSet手写最小堆heapq超时队列数据结构PriorityQueue手写最小堆heapq选玩顺序维护TreeSet 内建排序自定义比较函数元组天然比较超时顺序维护Comparator 三个字段自定义比较函数元组天然比较删除方式游玩侧物理删除超时侧延迟删除双延迟删除双延迟删除代码量中等偏多最少主要易错点key 还原、TreeSet remove手写堆比较函数输入解析类型从代码量看Python 最少因为元组比较和 heapq 直接解决了大部分问题。Java 最直观TreeSet 的 pollFirst 让游玩侧逻辑非常清晰。JS 则折中但手写堆模板有一定代码成本。5.3 机考中三语言怎么选如果目标是快速 AC且数据范围不大我会优先选 Python代码最短心智负担最小。但有些机考环境对 Python 执行时间卡得比较严或者 Python 版本较旧此时 Java 的 TreeSet 方案会更稳因为红黑树操作稳定不依赖解释器优化。如果只熟悉 JavaScript也不要慌堆模板背熟之后这道题完全能写。唯一要注意的是输入解析和输出格式Node.js 环境用fs.readFileSync(0, utf8)读取标准输入是最稳的做法。还有一点JS 的 Number 是双精度浮点但 10^5 级别的整数运算完全不会出现精度问题不需要用 BigInt。6. 题目背后的三类扩展与做题策略6.1 把“先到先玩”改成“让不开心人数最少”有些变体不会明确告诉你游玩顺序而是让你自己决定每轮让谁玩目标是让不开心的人数尽量少。这个版本就需要一点贪心思维每轮设施有空位时应该优先让“最容易超时”的人玩也就是 deadline 最小的人。因为你每拖一轮他就更接近超时临界点。实现上反而比原题更简单因为你只需要一个超时堆每轮从堆顶弹出 deadline 小于等于当前轮的人代表超时放弃然后再从堆顶选 deadline 最小的人去玩。这样能保证每个时间点都在尽可能抢救最紧迫的小朋友。这种变体我在别的题库里也见过核心模型几乎一样只是游玩排序规则不同。6.2 把“每轮固定 M 人”改成“每轮人数可调整”如果题目允许每轮根据排队人数动态决定接待多少个小朋友或者设施在不同轮次能力不同问题就变成了一个资源分配模型可能需要动态规划配合贪心。这种扩展已经把题目的难度抬高了一个层次通常不会出现在同一张试卷上但如果你遇到需要跳出“模拟”的框架去想。我的建议是刷题时先看数据范围。N、T 都小暴力模拟足够N、T 都在 10^5 左右双堆方案就是标准解如果还有额外的资源维度再考虑叠加其他数据结构。数据范围是选题思路的第一依据不要一上来就想复杂解法。6.3 刷这类题我推荐的三步走第一步手算样例。不要急着写代码先把题目给的样例在纸上跑一遍搞清楚超时判定发生在选人之前还是之后游玩顺序按什么排。这些规则一旦理解错后面的代码全白写。第二步朴素实现打底。即使你知道有优化方案也可以先写一个 O(N*T) 的版本用样例验证自己对题意的理解是否正确。我在做这道题时朴素版虽然提交超时但至少保证了逻辑上的正确性后续优化时可以用它来对拍。第三步对拍验证。优化版写完以后用随机小数据把两个版本的结果反复对比。我当时专门写了一个小脚本随机生成 N 和 T 都在 20 以内、M 在 5 以内的数据跑了上千组确认双堆版本的输出和朴素版本完全一致才敢提交。延迟删除这种逻辑靠肉眼检查很难发现漏判对拍是最可靠的验证方式。这道题做完我最大的收获不是记住了双堆解法而是理解了“双堆延迟删除”这套组合背后的适用条件当一个集合需要同时以两种不同维度做优先级操作时不要试图用一个结构硬存两个结构各自维护一种优先级再用状态数组兜底才是清晰的解法。以后遇到类似题目哪怕结构不同这套思路也能直接迁移。最后一个小建议任何涉及“逻辑删除”的模拟题状态数组一定要在每次弹出后、业务操作前检查顺序错一点输出就全错了。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
