第一次看到《不开心的小朋友》这个题目时，我以为是道脑筋急转弯，想考什么心理学的“情绪管理”。点进去一看，好家伙，是一道 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这里 N=5，M=1，T=4，设施每轮只能接待 1 个小朋友。
逐轮模拟：
| 轮次 | 本轮到达 | 超时检查 | 本轮游玩 | 离开 |
|---|---|---|---|---|
| 1 | 1号、2号 | 无 | 1号 | 无 |
| 2 | 3号 | 无 | 2号 | 无 |
| 3 | 4号、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号已经在等待区里等了一轮，耐心值是 0，1 大于 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号：a=2，t=0，deadline=3，所以第 3 轮开头就离开。5号：a=3，t=0，deadline=4，所以第 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(); List<List<Integer>> 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); } TreeSet<Long> waiting = new TreeSet<>(); PriorityQueue<long[]> 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]; List<Integer> 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 和 hashCode，remove 就会失效，这是 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 三语言实现对比
| 对比项 | Java | JavaScript | Python |
|---|---|---|---|
| 等待队列数据结构 | 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 以内的数据，跑了上千组，确认双堆版本的输出和朴素版本完全一致，才敢提交。延迟删除这种逻辑，靠肉眼检查很难发现漏判，对拍是最可靠的验证方式。
这道题做完，我最大的收获不是记住了双堆解法，而是理解了“双堆+延迟删除”这套组合背后的适用条件：当一个集合需要同时以两种不同维度做优先级操作时，不要试图用一个结构硬存，两个结构各自维护一种优先级，再用状态数组兜底，才是清晰的解法。以后遇到类似题目，哪怕结构不同，这套思路也能直接迁移。最后一个小建议：任何涉及“逻辑删除”的模拟题，状态数组一定要在每次弹出后、业务操作前检查，顺序错一点，输出就全错了。
