企业官网建设流程全解析

【题目来源】

学而思编程：约瑟夫游戏（三）

【题目描述】

有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_i=12ai​=12，则第i ii轮游戏结束后，最后一个被数到的小朋友为16 1616号小朋友，他将被淘汰出局，并且处于其下一位的第8 88号小朋友将被指定为新领头人。

现在，请你求出每一轮被淘汰的小朋友的编号。

【输入】

第一行两个整数n nn，k 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

【核心思想】

1. 问题分析：n nn个小朋友围成一圈，进行k kk轮淘汰。每轮从当前领头人的下一位开始顺时针数a i a_iai​个人，最后数到的人淘汰，其下一位成为新领头人。求每轮淘汰者的编号。这是一个队列模拟 + 取模优化问题，关键在于用队列维护当前存活者顺序，并通过取模避免无效循环。

2. 算法选择：

   • 队列模拟：用队列存储当前存活的小朋友编号，队首即为当前领头人
   • 取模优化：a i a_iai​可能很大，对当前存活人数取模后只需移动少量元素
   • 循环移位：将队首x xx个元素依次移到队尾，模拟顺时针数数过程

3. 关键步骤：

   • 初始化：
     • 读取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()：将淘汰者移除队列
   • 队首自动更新为新领头人，进入下一轮

4. 时间/空间复杂度：

   • 时间复杂度：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个元素

5. 队列模拟的核心思想：

   • 循环结构映射：将环形结构映射为队列的循环移位，队首代表当前位置，队尾代表"绕回"的位置，天然模拟顺时针顺序
   • 取模降维：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 特性完美契合"顺时针顺序数数"的语义
   • 适用于"环形淘汰 + 顺序报数"类问题，队列配合取模可将大规模报数优化到线性规模

【算法标签】

#队列

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn,k,a[105],now,cnt;// n: 总人数，k: 出局人数，a: 报数序列，now: 当前位置，cnt: 计数boolb[105];// 标记是否已出局intmain(){cin>>n>>k;// 输入总人数n和出局人数kfor(inti=1;i<=k;i++)// 输入报数序列{cin>>a[i];}for(inti=1;i<=k;i++)// 进行k轮出局{cnt=0;// 计数清零intm=a[i]%(n-i+1);// 计算实际需要数的人数（考虑循环）while(cnt<=m)// 数m+1个人（包括起点）{now=(now+1+n-1)%n+1;// 移动到下一个位置，循环处理if(b[now]==0)// 如果当前位置的人未出局cnt++;// 计数加1}b[now]=1;// 标记当前位置的人出局cout<<now<<" ";// 输出出局的人的编号}return0;}

#include<bits/stdc++.h>usingnamespacestd;intmain(){queue<int>q;// 队列存储人员编号intn,k;cin>>n>>k;// 输入总人数n和操作次数k// 初始化队列，人员编号1~nfor(inti=1;i<=n;i++){q.push(i);}while(k--)// 执行k次操作{intx;cin>>x;// 输入本轮要移动的位置数// 取模，避免重复移动x=x%q.size();// 将前x个人移到队尾for(inti=0;i<x;i++){q.push(q.front());// 队首元素移到队尾q.pop();// 移除队首}// 输出当前队首（要淘汰的人）cout<<q.front()<<" ";// 淘汰这个人q.pop();}return0;}

【运行结果】

7 5 10 4 11 4 1 4 2 5 6 1