【题目来源】学而思编程约瑟夫游戏三【题目描述】有n nn个小朋友围成一圈玩数数游戏。小朋友们按顺时针顺序依次编号为1 ∼ n 1\sim n1∼n。初始时1 11号小朋友被指定为领头人。游戏一共会进行k kk轮。在第i ii轮中领头人会从他的顺时针方向的下一个人开始按顺时针顺序数a i a_iai​个人。其中最后一个被领头人数到的人被淘汰出局这也意味着该轮游戏结束。出局者的顺时针方向的下一个人被指定为新领头人引领新一轮游戏。例如假设当游戏即将开始第i轮时还剩下5 55个小朋友编号按顺时针顺序依次为8 , 10 , 13 , 14 , 16 8,10,13,14,168,10,13,14,16并且当前领头人为13 1313号小朋友a i 12 a_i12ai​12则第i ii轮游戏结束后最后一个被数到的小朋友为16 1616号小朋友他将被淘汰出局并且处于其下一位的第8 88号小朋友将被指定为新领头人。现在请你求出每一轮被淘汰的小朋友的编号。【输入】第一行两个整数n nnk kk第二行k kk个整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1​,a2​,…,an​。【输出】一行k kk个整数其中第i ii个整数表示在第i ii轮中被淘汰的小朋友编号。【输入样例】7 5 10 4 11 4 1【输出样例】4 2 5 6 1【核心思想】问题分析n nn个小朋友围成一圈进行k kk轮淘汰。每轮从当前领头人的下一位开始顺时针数a i a_iai​个人最后数到的人淘汰其下一位成为新领头人。求每轮淘汰者的编号。这是一个队列模拟 取模优化问题关键在于用队列维护当前存活者顺序并通过取模避免无效循环。算法选择队列模拟用队列存储当前存活的小朋友编号队首即为当前领头人取模优化a i a_iai​可能很大对当前存活人数取模后只需移动少量元素循环移位将队首x xx个元素依次移到队尾模拟顺时针数数过程关键步骤初始化读取n nn总人数和k kk轮数创建队列将1 11到n nn依次入队执行k kk轮淘汰读取本轮报数a i a_iai​x a_i \bmod q.size()对当前存活人数取模得到实际需要移动的位置数循环x xx次q.push(q.front())将队首元素移到队尾q.pop()移除原队首此时队首即为要数到的第a i a_iai​个人淘汰者输出q.front()q.pop()将淘汰者移除队列队首自动更新为新领头人进入下一轮时间/空间复杂度时间复杂度O ( k × max ⁡ ( a i m o d 当前人数 ) ) O(k \times \max(a_i \bmod \text{当前人数}))O(k×max(ai​mod当前人数))取模后每轮最多移动O ( n ) O(n)O(n)次总复杂度O ( k × n ) O(k \times n)O(k×n)空间复杂度O ( n ) O(n)O(n)队列最多存储n nn个元素队列模拟的核心思想循环结构映射将环形结构映射为队列的循环移位队首代表当前位置队尾代表绕回的位置天然模拟顺时针顺序取模降维a i a_iai​可能远大于当前存活人数利用a_i % q.size()将移动次数压缩到[ 0 , size − 1 ] [0, \text{size}-1][0,size−1]避免O ( a i ) O(a_i)O(ai​)的无效操作领头人自动维护淘汰者出队后原队首淘汰者的下一位自动成为新领头人无需额外标记约瑟夫问题的队列解法经典约瑟夫问题的变体队列的 FIFO 特性完美契合顺时针顺序数数的语义适用于环形淘汰 顺序报数类问题队列配合取模可将大规模报数优化到线性规模【算法标签】#队列【代码详解】#includebits/stdc.husingnamespacestd;intn,k,a[105],now,cnt;// n: 总人数k: 出局人数a: 报数序列now: 当前位置cnt: 计数boolb[105];// 标记是否已出局intmain(){cinnk;// 输入总人数n和出局人数kfor(inti1;ik;i)// 输入报数序列{cina[i];}for(inti1;ik;i)// 进行k轮出局{cnt0;// 计数清零intma[i]%(n-i1);// 计算实际需要数的人数考虑循环while(cntm)// 数m1个人包括起点{now(now1n-1)%n1;// 移动到下一个位置循环处理if(b[now]0)// 如果当前位置的人未出局cnt;// 计数加1}b[now]1;// 标记当前位置的人出局coutnow ;// 输出出局的人的编号}return0;}#includebits/stdc.husingnamespacestd;intmain(){queueintq;// 队列存储人员编号intn,k;cinnk;// 输入总人数n和操作次数k// 初始化队列人员编号1~nfor(inti1;in;i){q.push(i);}while(k--)// 执行k次操作{intx;cinx;// 输入本轮要移动的位置数// 取模避免重复移动xx%q.size();// 将前x个人移到队尾for(inti0;ix;i){q.push(q.front());// 队首元素移到队尾q.pop();// 移除队首}// 输出当前队首要淘汰的人coutq.front() ;// 淘汰这个人q.pop();}return0;}【运行结果】7 5 10 4 11 4 1 4 2 5 6 1