7.15队列练习

排队P9518题解复盘基本信息项目内容题目编号、来源P9518 / 排队模拟训练层级B 队列模拟知识版块队列、模拟、哈希表、迭代器解题前・关键信号识别维度分析目标、约束、底层结构目标模拟游戏机排队系统支持 start开始游戏、arrive到达排队、leave离开队列三种操作约束n ≤ 1e5人名长度 ≤ 10底层结构需要维护排队顺序队列快速判重集合快速删除队列中任意元素list 迭代器映射。数据规模n ≤ 1e5O(n) 或 O(n log n) 均可人名仅含大小写字母。候选算法和依据方案一queue set 我的写法TLE方案二list unordered_set unordered_map 存迭代器O(1) 删除题解写法。复杂度预判时间复杂度 O(n)每个操作均摊 O(1)空间复杂度 O(n)。解题后・外化复盘从会一次到稳定会维度内容实现结构 / 核心思路第一步用liststring q存储排队队列包含正在游玩的人放在队首用string a, b记录正在游玩的两人用unordered_setstring us记录正在排队的人不包括 a 和 b用unordered_mapstring, liststring::iterator um记录每个人在 list 中的位置第二步处理三种操作arrive检查是否已在队列中若否则入队并记录位置leave检查是否在排队且未游玩若是则通过迭代器 O(1) 删除start将上一局游玩的人从队首移到队尾再从队首取 1~2 人上场放到队首。错因回溯逻辑BUG / 代码实现BUG1. arrive 时忘记检查是否正在游玩导致已在游玩的人可以重复入队2. start 时取第二个人后没有从队列中弹出导致队列状态错误3. 用 queue 实现时 leave 需要遍历整个队列 O(n)大数据超时后来看题解学会了list和list::iterator的用法边界和易错点1. start 时队列为空输出 Error2. start 时队列只有 1 人只输出 1 人3. arrive 时已在队列中或正在游玩 → Error4. leave 时不在队列中或正在游玩 → Error5. 上一局的人放回队尾的顺序是 a 先 b 后6. 用 list 存储时迭代器在删除其他元素时不会失效除被删除的那个。下次看到什么信号我应该想到这个方法看到「排队 中间删除 判重 O(1) 删除」用 list unordered_map 存迭代器。AC 完整代码list 迭代器版#includebits/stdc.husingnamespacestd;liststringq;string a,b;unordered_setstringus;unordered_mapstring,liststring::iteratorum;intmain(){intn;cinn;while(n--){string s;cins;if(sstart){if(q.empty()){puts(Error);continue;}if(a!){q.push_back(a),q.pop_front();um[a]--q.end();}if(b!){q.push_back(b),q.pop_front();um[b]--q.end();}aq.front();q.pop_front();if(!q.empty()){bq.front();}else{b;}q.push_front(a);um[a]q.begin();couta;if(b!)cout b;coutendl;}elseif(sarrive){string k;cink;if(us.find(k)!us.end()){puts(Error);continue;}q.push_back(k);um[k]--q.end();us.insert(k);puts(OK);}elseif(sleave){string k;cink;if(ka||kb||us.find(k)us.end()){puts(Error);continue;}q.erase(um[k]);us.erase(us.find(k));puts(OK);}}return0;}