信息学奥赛一本通1332这道“周末舞会”可以说是队列章节里最经典的开门题。第一次看题面很多人觉得“这不就是个模拟吗”但真正动手写的时候才会意识到队列的先进先出规则、循环入队的时机、边界条件的处理全都在这个看似简单的例子里埋着。这道题适合所有刚接触数据结构的选手尤其是准备NOIP普及组、CSP-J或者校内信息学竞赛的同学吃透它队列这个知识点的地基就算打牢了一半。整道题的价值在于它用一场舞会把“队首出队、队尾入队”这件事讲得非常直观但你如果只是背代码而不理解数据流动遇到变式题照样懵。所以这篇博文我打算把题目拆开揉碎从队列原理讲到代码实现再把手写模拟和STL两种写法都过一遍最后整理我这两年看到学生最常踩的坑以及这类题目的通用套路。1. 题目到底在考什么——从“周末舞会”看队列的核心思想1.1 题目描述与样例拆解先还原一下题目场景。周末舞会上男士和女士分别排成两队。舞会开始时主持人会依次安排两队队首的男士和女士出来配对跳舞。每跳完一支舞曲这两位舞伴并不会离开而是分别回到自己队伍的末尾继续排队。题目输入三个数男士人数m、女士人数n、舞曲数量k要求输出前k支舞曲中每一轮配对的是几号男士和几号女士。这个题面看起来只是“排队配对”但它其实精准地考察了一个核心概念队列的FIFOFirst In First Out先进先出特性。男士队和女士队各自遵守“先到先跳跳完排到末尾”的规则这恰好就是队列的操作方式——出队发生在队首入队发生在队尾。标准输入样例通常是3 4 6对应的输出为1 1 2 2 3 3 1 4 2 1 3 2拿这个样例走一遍你会发现男士队始终在1、2、3之间循环因为只有3个人女士队则在1、2、3、4之间循环因为人数不同两队的轮转节奏不一样所以会出现“1号男士配上4号女士”、“2号男士配上1号女士”这种错位组合。这正是队列模拟最有意思的地方两个长度不同的循环队列相位会不断变化。1.2 为什么这道题是队列的“教科书例题”我见过不少学生刷题时直接背STL的queue写法代码跑通就觉得会了。但“周末舞会”能成为一本通里的【例2-1】不是因为它简单而是因为它把队列的每一个基本操作都暴露在了明面上初始化两个队分别按编号从小到大入队。出队配对每轮从男队、女队各取一个队首元素。入队续排配对完成后把这两名舞者分别塞回各自队伍的末尾。循环执行重复上述过程k轮。如果只是把queue当成一个“能存数据的数组”来用那就完全失去了这道题的教学意义。正确的理解方式应该是把队列看成一个“管道”数据从尾部流入、从头部流出流出的数据如果还需要参与后续过程就得再次从尾部流入。周末舞会的男士、女士就是不断在管道里循环流动的数据。队列的这种“环形流水线”模型在后面的广度优先搜索BFS、拓扑排序、单调队列等更复杂的算法里会反复出现。所以这道例题刷透的价值不在于AC本身而在于帮你建立“队列是动态过程”的直觉。1.3 数组模拟 vs STL queue选哪个代码实现上通常有两种选择直接用C STL的queue容器或者自己用数组模拟队列。我的建议是刚开始学的时候两种都要会写而且一定要先搞懂数组模拟再去用STL这样才能真正理解“队首指针”和“队尾指针”到底在干什么。用STL queue写代码非常简洁#include bits/stdc.h using namespace std; int main() { int m, n, k; cin m n k; queueint men, women; for (int i 1; i m; i) men.push(i); for (int i 1; i n; i) women.push(i); for (int i 1; i k; i) { int boy men.front(); men.pop(); int girl women.front(); women.pop(); cout boy girl endl; men.push(boy); women.push(girl); } return 0; }但数组模拟的代码会让你看到队列的本质。数组模拟的通用逻辑是开一个足够大的数组用head指针指向队首用tail指针指向队尾下一个可写位置入队就是a[tail]x出队就是head。因为本题中舞者要回到队尾所以数组需要开大一些最多容纳“初始人数 轮数”个元素或者更稳妥的做法是用循环队列来节省空间。不管用哪种写法核心循环逻辑都是完全一样的先取队首再弹出输出配对最后把取出的元素重新入队。这个顺序不能乱尤其是“先输出再入队”还是“先入队再输出”虽然结果一样但逻辑上应该保持“配对完成再回队尾”的语义。2. 手把手解题从模拟过程到代码实现2.1 手算模拟一轮舞会看懂数据流动我强烈建议初学者在写代码之前先拿笔在纸上手动模拟几轮。以m3n4为例初始状态男士队1 2 3队首是1女士队1 2 3 4队首是1第1轮1号男士和1号女士出队配对输出“1 1”然后两人分别回到队尾。男士队变成2 3 1女士队变成2 3 4 1第2轮2号男士和2号女士配对输出“2 2”然后回队尾。男士队3 1 2女士队3 4 1 2第3轮3号男士和3号女士配对输出“3 3”然后回队尾。男士队1 2 3女士队4 1 2 3第4轮1号男士和4号女士配对输出“1 4”。男士队2 3 1女士队1 2 3 4第5轮2号男士和1号女士配对输出“2 1”。男士队3 1 2女士队2 3 4 1第6轮3号男士和2号女士配对输出“3 2”。手动模拟的意义在于你会亲眼看到两个队的“队首”在不断变化尤其是“回队尾”这个动作会让原本排在最前面的人在一段时间后重新轮到。这个“循环感”一旦建立起来写代码时就不会把front和pop的顺序搞混。2.2 数组模拟队列的详细实现如果你用的是C语言风格或者想避免STL的隐藏开销数组模拟是更底层的写法。这里我给出一个带注释的完整版本#include cstdio const int MAXN 10005; // 足够容纳初始人数 轮数 int main() { int m, n, k; scanf(%d%d%d, m, n, k); // 数组模拟队列qmen存男士编号qwomen存女士编号 int qmen[MAXN], qwomen[MAXN]; int hmen 0, tmen m; // 男士队头指针、尾指针 int hwomen 0, twomen n; // 女士队头指针、尾指针 for (int i 1; i m; i) qmen[i - 1] i; for (int i 1; i n; i) qwomen[i - 1] i; for (int i 1; i k; i) { int boy qmen[hmen]; // 队首男士出队 int girl qwomen[hwomen]; // 队首女士出队 printf(%d %d\n, boy, girl); qmen[tmen] boy; // 男士回到队尾 qwomen[twomen] girl; // 女士回到队尾 } return 0; }这段代码里最容易理解错的是指针的含义。hmen指向的是当前队首元素在数组中的下标tmen指向的是“下一个入队元素存放的位置”所以初始时男士数组的0到m-1分别存1到mtmenm表示下一个空位是下标m。出队操作qmen[hmen]会先取出hmen位置的值然后指针后移入队操作qmen[tmen]boy会先把boy存到tmen位置然后指针后移。因为每次配对后两个人都回到队尾所以队列长度始终不变但数组下标会一直增长这也是为什么数组要开大一些。MAXN开到10005其实就是假设“mnk”不超过这个范围在正常情况下绰绰有余因为一本通里这题的数据范围很小。2.3 两种写法对比什么场景用哪种STL queue的优势是代码量少、语义清晰不容易因为指针操作出错劣势是如果你不理解内部机制遇到需要访问队列中间元素或者做循环队列优化时会觉得无从下手。数组模拟的优势是让你看到“指针移动”的本质而且可以灵活控制队列的容量和访问方式缺点是容易在边界条件上翻车。我个人的建议分阶段刚开始学队列用STL queue先AC目标是理解队列操作。学完以后马上用数组模拟重写一遍目标是理解机制。刷题阶段根据题目需求选择。如果只是简单的入队出队STL足够如果涉及循环队列、双端队列、需要下标计算的题目用数组模拟更可控。这里有个很容易被忽视的细节STL的queue底层默认是deque双端队列实现的频繁push、pop本身不会有性能问题但如果数据类型很大或者操作次数达到百万级还是建议用数组模拟或者手写循环队列。周末舞会的数据量完全不需要担心怎么写都行。3. 那些“一本通”里没写明白的坑与排查技巧3.1 常见错误1人数、轮数边界搞反这题的输入是m、n、k分别表示男士人数、女士人数、舞曲轮数。我见过有同学把顺序读成m、k、n或者把样例里的“3 4 6”理解成“3轮、4个男士、6个女士”。这种错误纯属审题不仔细但一旦发生排查起来很费时间因为程序能跑、输出也是合法的数字对只是结果和样例对不上。我的经验是读题后先别急着写代码把三个变量分别标注清楚写注释“m男士人数n女士人数k轮数”。在代码开头加一句注释成本极低但能帮你在赛后回看时快速恢复上下文。还有一个小技巧自己构造一个极简数据比如“1 1 3”输出应该是三次“1 1”。如果连这种数据都输出不对说明逻辑存在根本性问题和样例数据对不对得上反而次要。3.2 常见错误2出队入队顺序写错导致死循环用STL queue时常见的错误写法是把“取队首”和“弹出”的顺序弄反比如int boy men.front(); int girl women.front(); cout boy girl endl; men.pop(); women.pop(); men.push(boy); women.push(girl);这段代码本身没毛病front和pop的顺序只要保证“先取值再弹出”就行。但如果你写成这样men.pop(); int boy men.front();那就出大问题了。因为pop会移除队首元素如果你在pop之后再去取front取到的是原来第二个元素也就是下一轮才该出场的人。在这种写法下第一轮配对的人变成了2号男士和2号女士后面的轮次也会整体错位。更危险的情况是如果你在pop之后又尝试push同样的元素队列的逻辑就乱了极端情况下可能造成死循环或者输出明显异常。所以我的建议是养成“先保存队首值再pop再push回队尾”的固定习惯。顺序永远是取、删、插。3.3 常见错误3输入输出格式问题一本通的评测系统对输出格式非常严格行尾空格、空行、换行符都可能导致格式错误。这道题要求每行输出两个整数中间用空格隔开。有些同学写完代码后喜欢加上额外的空行或者把数字对用逗号分隔这在本地编译器里看着没问题交上去就是Presentation Error。另外如果使用printf输出注意格式串里不要有多余的空格比如printf(%d %d\n, boy, girl)是对的但printf(%d %d\n, boy, girl)两个空格在某些SPJ下没问题在普通题目下也可能判对但不值得冒这个险。C的cout输出则要注意endl和\n的区别性能上在本题无所谓但竞赛中大量输出时endl因为要刷新缓冲区会比\n慢不少这里也顺手养成用\n的习惯。3.4 常见问题速查表症状可能原因排查方法输出第一行就是“2 2”先pop后取front取到了第二个元素检查front和pop的先后顺序输出一直重复同一对组合入队操作写在输出之前且只push了一次或while循环条件有误检查循环体是否完整包含取、删、插三步数组越界程序崩溃数组开太小或者队尾指针越界确认数组大小至少为nmk输出格式错误多空格、多空行、用了中文符号对照样例输出逐字符检查样例能过但提交WA变量含义理解错或者题目要求输出前k个配对但理解成第k个重新读题确认“前k轮”的含义这题最常见的“玄学错误”其实是把m和n当成了男女编号的上限但实际题目中男士编号就是1到m女士编号就是1到n这一点并不复杂。复杂的是你自己在调试时脑补出来的“编号可能从0开始”之类的问题所以动手写之前先明确“队列初始元素是1到m、1到n”。4. 从周末舞会到更多题型队列模拟的通用套路4.1 队列模拟的通用模板在刷过“周末舞会”之后你会发现大量模拟类题目都遵循类似的模式。我把这个模式抽象成四步模板适配大部分队列模拟题初始化队列按题目给定的顺序把初始数据依次入队。循环处理根据题目要求的轮数或条件重复执行循环体。出队操作从队首取出需要处理的数据。回队尾或丢弃根据题目语义决定处理完的数据是回到队尾继续排队还是直接移除。这个模板的关键在于第4步。周末舞会里每个人跳完舞要回队尾所以取出的元素要再push回去。约瑟夫问题是报到数的人出局那就不能回队尾。卡片游戏比如把第一张放最下面、第二张丢出去则是混合操作有些元素要回队尾有些要丢弃。模板本身不会变变的是你对“处理完的数据去向”的判断。写这类题的时候我习惯先在注释里写清楚“这个元素处理完之后去哪”相当于给代码加了一张数据流向说明调试时能少走很多弯路。4.2 同类变式题约瑟夫问题、报数问题、卡片游戏信息学奥赛里队列模拟的经典变式非常多这里讲几个最常见的第一个是约瑟夫问题Josephus Problem。n个人围成一圈从第一个人开始报数报到m的人出列然后从下一个人开始继续报数求所有人的出列顺序。解法是用队列模拟每次把队首的人移到队尾相当于让他“报数但没报到m”报到m的人直接弹出不回到队尾。这个变式的核心就是用“回队尾”代替“围成一圈”逻辑上非常优雅。第二个是报数问题。比如一群人围成一圈从1开始报数报到3的人退出然后从1重新报数问最后剩下的是几号。这题和约瑟夫几乎一样用队列模拟时每次循环执行两次“移动队首到队尾”第三次“弹出队首”就能完成一轮报数。写的时候要注意弹出之后不要再次移动否则会漏人。第三个是卡片游戏。比如有一摞卡片每次把第一张放到最下面然后把新的第一张丢出去直到只剩一张牌按丢出顺序输出卡片。这个就直接按照“取出队首、放回队尾、再取出队首、丢弃”的顺序循环即可。这类题在《一本通》后面的练习里经常出现本质都是队列操作只是“出队数据”是否回到队尾的决策不同。这几道题放在一起看你会发现它们考的都是“队列里元素的生命周期管理”。周末舞会的舞者生命周期最长从头到尾都在循环约瑟夫问题里出局的人生命周期结束会被移出队列。你只要能判断出“每个元素在什么条件下出队、什么条件下回队尾”就能解决一整类模拟题。4.3 队列还能解决什么什么时候别用队列除了模拟题队列在算法里的应用也非常广泛。BFS广度优先搜索就是以队列为核心数据结构从起始节点出发把可到达的节点依次入队再逐个出队扩展。拓扑排序也用队列维护“当前入度为0”的节点集合。滑动窗口最大值这道经典题用的是单调队列队列里存的元素保持单调性所以能快速获取窗口内的最值。但队列也不是万能的。如果需要频繁访问队列中间的元素或者需要在队列头部插入元素标准queue就不好用了这时候该考虑vector、list或deque。比如周末舞会如果换成“随机指定某个人站到队首”那就不是队列模型而是更复杂的线性表操作。所以做题时先判断数据操作模式再选择数据结构而不是看题目字面里有没有“排队”。5. 关于“弗洛伊德算法”搜索词的一个提醒5.1 为什么有的搜索会关联到弗洛伊德在搜“信息学奥赛一本通 周末舞会”的时候有些网站的热搜关联里会出现“弗洛伊德算法”这容易让刚入门的人产生困惑以为这道题需要用到图论里的多源最短路径算法。实际上这是典型的“关联推荐误伤”因为“信息学奥赛一本通”这套书覆盖的知识点很多弗洛伊德算法Floyd-Warshall是书中图论章节的经典内容和队列章节的周末舞会没有任何关系。我在带学生的过程中没少遇到这类问题学生在搜索引擎里看到了不相关的关联词误以为题目难度很大还没动手就先怯了。所以这里专门说一下周末舞会的核心数据结构就是队列跟弗洛伊德算法半点关系都没有。如果你是为了准备比赛不要因为关联词就跑去提前学多源最短路先把队列基础打扎实更重要。如果确实对弗洛伊德算法感兴趣可以把它放到图论章节去学那又是一个新的框架它用三重循环更新任意两点之间的最短路径时间复杂度O(n^3)。它的代码里虽然也会用数组维护状态但和队列模拟的思路完全不同两者放在一起学容易互相干扰。5.2 队列和“最短路”家族其实也有交集不过话说回来队列和最短路径算法并非毫无交集。图论里有一个SPFA算法全称是Shortest Path Faster Algorithm它的核心操作就是用队列维护“待松弛的节点”。每次从队首取出一个节点尝试用它去更新邻居的最短距离如果某个邻居的距离被更新了就把它加入队尾。这和周末舞会的“出队、处理、入队”结构有几分相似但处理的逻辑完全不同。我提这个是想说明队列是一种基础数据结构它的适用场景极其广泛。你在一本通第二章学到的队列操作会在之后的图论算法里反复出现。所以千万别认为“周末舞会这种模拟题太简单不值得认真学”。恰恰相反真正把队列的入队、出队、循环机制理解透后面学SPFA、BFS的时候会轻松很多。当然如果你现在才刚到队列这一章完全不用理会SPFA和弗洛伊德把周末舞会AC了再把约瑟夫问题、报数问题这些变式练一遍就非常好。学算法最忌讳的就是贪多嚼不烂每个阶段该掌握什么就掌握什么。6. 调试与验证用自己的方法确认代码正确6.1 万能的手算验证法代码写完后不要急着提交先用手算数据验证。拿样例“3 4 6”来说你可以在草稿纸上画两队每轮用箭头标出队首是谁然后和程序输出比对。如果能对上说明基本逻辑没问题。但这个验证方法有一个盲区样例太简单不一定能覆盖所有边界情况。所以我还会额外测试几组数据m1, n1, k5输出应该是五行“1 1”验证循环是否正常。m5, n2, k10女士队只有2个人输出应该能看到女士编号在1、2之间来回交替。k0没有舞曲理论上什么都不输出。这种边界数据在OJ上不太常见但能帮你确认循环条件写的是ik还是ik。尤其是“k0”这种情况如果循环条件写成“i1; ik; i”当k为0时输出为空看起来正常但如果写成“do-while”或者“while(k--)”k为0时可能多输出一轮这种问题一旦出现很难查。所以写循环前先想清楚是“执行k轮”那么循环次数必须严格等于k。6.2 利用输出插值定位问题如果代码输出错误最简单的排查方法是在循环体里加调试输出打印每一轮开始时两个队列的队首和队尾状态。比如cout Round i : men front men.front() , women front women.front() endl;这个调试输出在本地运行时会打印出每一轮的队列状态方便你对照手算过程定位是出队错了还是入队错了。排查完记得删除调试输出不然提交时会多打印一堆无关内容直接WA。如果你用的是数组模拟还可以打印hamen、tmen、hwomen、twomen四个指针的值检查指针移动是否符合预期。指针问题往往比逻辑问题更难发现因为数组越界不一定立刻崩溃可能会在某个运行阶段才报错。6.3 对比STL和数组模拟的双保险我有一次在课堂上让几个学生同时用STL queue和数组模拟写这道题结果双方代码都AC了但中间有一版数组模拟的代码因为数组开得不够大在本地测试大数据时出现乱码而STL版本完全正常。这件事给我的启发是对于入门题交叉验证非常有效。如果你写的是数组模拟版可以再用STL queue写一版如果两版输出一致那代码逻辑基本可靠。这种做法在正式比赛中不现实但在学习阶段是很好的自我检查手段。另外如果你发现自己的数组模拟版在特定数据下输出怪异优先检查数组大小。m、n很小的时候没问题但k一大队尾指针会一直增长如果数组开小了写入就会越界。稳妥起见数组大小最少开到“m n k 10”。一本通的数据范围很小开10005通常足够了但养成“多开10个单位”的习惯能避免很多莫名奇妙的运行时错误。7. 从例题到赛场这一类模拟题的应试策略7.1 竞赛中如何快速识别队列模拟题信息学竞赛的题目不会像一本通这样直接告诉你“这一章是队列”所以在真实赛场上你需要具备识别题目类型的能力。一般来说出现这些特征时可以考虑用队列模拟题目里有“排队”“轮流”“循环”“依次”等关键词。所有元素都遵循“先到先处理”的顺序。处理完的元素可能重新排队比如回到队尾或者直接移除。数据规模不大允许用模拟的方式直接运算。就拿周末舞会来说“配对的两个人回到队尾重新排队”是决定用队列的关键特征。如果题目改成“配对后就离开”那其实更像顺序访问数组不一定需要队列。所以审题时重点看“元素处理完之后的去向”而不是题目表面有没有出现“队”这个字。7.2 时间复杂度与空间复杂度估算像“周末舞会”这类模拟题k最大如果到1000或10000单轮操作只有常数次总时间复杂度是O(k)完全没问题。即使k到100万O(k)也通常能过。但如果你不小心把实现写成“每次查找两个人”O(k*mn)数据一大就会超时。空间方面如果直接用STL queue初始入队mn个元素后面的push和pop数量与k有关但queue内部会自动扩容不用担心。如果用数组模拟就要手动估算最大需要的容量。一张快速估算的公式是初始元素数 总入队次数 m n k。因为每轮最多入队两个元素男士、女士各一个但初始已经占了mn个位置所以数组总大小至少为mn2k。但实际操作中男士队列和女士队列是分开的男士队最多同时存在元素不超过mk中男士入队次数而男士每轮都会入队一次所以男士队列数组至少需要mk女士队列至少需要nk。稳妥做法是直接开一个大数组比如100000完全避开边界问题。这些估算方法一开始可能觉得烦但养成习惯后你在赛场上就不会因为数组越界白白丢分。7.3 赛前刷题顺序建议如果你正在准备CSP-J或NOIP普及组我的建议是把一本通队列这一章的例题和课后题按顺序刷完确保每一道都能用STL queue和数组模拟两种写法AC。周末舞会是最简单的一道可以作为“热身题”紧接着的报数问题、约瑟夫问题可以作为“进阶题”再往后的BFS相关题目比如迷宫最短路才是队列知识点的真正考验。刷题时不要满足于AC每道题提交通过后可以问自己三个问题队列里每个元素的入队和出队条件是什么有没有不需要队列也能解的方法如果把题目改成另一种数据规模我的代码还成立吗这三个问题能帮你把一道题的价值榨干。我见过很多学生刷题数量不少但遇到同类题还是不会原因就是刷题时只关注“能不能过样例”没有去理解题目背后的数据结构模型。周末舞会这道题如果你能用自己的话把“为什么用队列、队列里数据怎么流动、循环何时终止”讲清楚那才是真正学懂了。最后再说一个我在实际教学中很常用的小技巧学完这道题后不要急着看下一题试着把“周末舞会”改造成其他场景比如“早高峰地铁排队上车间”、“食堂打饭循环排队”用同样的队列逻辑去模拟这些生活场景。多玩几次这样的“移植”你对队列的理解会远超只刷题目的同学。
