csp信奥赛C++标准模板库STL案例应用14-开发者社区

csp信奥赛C++标准模板库STL案例应用14

queue实践

题目描述

n nn个人围成一圈，从第一个人开始报数,数到m mm的人出列，再由下一个人重新从1 11开始报数，数到m mm的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。

输入格式

输入两个整数n , m n,mn,m。

输出格式

输出一行n nn个整数，按顺序输出每个出圈人的编号。

输入输出样例 1

输入 1

10 3

输出 1

3 6 9 2 7 1 8 5 10 4

说明/提示

1 ≤ m , n ≤ 100 1 \le m, n \le 1001≤m,n≤100

思路分析

这是一个经典的约瑟夫环问题。代码使用队列这种数据结构来模拟整个过程：

初始状态：n个人围成一圈，编号1~n
报数规则：从第一个人开始报数，数到m的人出圈
循环过程：出圈后，从下一个人继续从1开始报数
结束条件：所有人都出圈

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,m;// 总人数n，报数上限mqueue<int>q;// 使用队列模拟约瑟夫环intmain(){// 输入数据cin>>n>>m;// 初始化队列：将1~n的编号顺序入队// 此时队列中的顺序就是初始的环状顺序for(inti=1;i<=n;i++){q.push(i);}// 模拟出圈过程while(!q.empty()){// 关键步骤：将前m-1个人从队首移到队尾// 这模拟了"报数"过程：这些人报数不是m，所以不出圈for(inti=1;i<=m-1;i++){q.push(q.front());// 队首元素加入队尾（相当于回到圈中继续报数）q.pop();// 移除原队首元素}// 当前队首即为报数到m的人// 因为前m-1个人已经移到队尾，现在队首是第m个人cout<<q.front()<<" ";// 输出出圈编号q.pop();// 移除已出圈的人（此人离开队列）}return0;}

功能分析

1. 核心数据结构：队列

队列的特性：先进先出（FIFO）
模拟环状结构：通过出队再入队的方式，模拟了人围成一圈的效果
队首代表当前报数的人：始终从队首开始报数

2. 算法流程

初始化：1 2 3 ... n 入队 循环直到队列为空： 1. 将前m-1个人移到队尾（报数过程） 2. 队首的人出队并输出（出圈）

3. 示例演示（n=5, m=3）

初始队列：[1,2,3,4,5] 第1轮：1,2移到队尾 → [3,4,5,1,2] → 3出圈 第2轮：4,5移到队尾 → [1,2,4,5] → 1出圈 第3轮：2,4移到队尾 → [5,2,4] → 5出圈 第4轮：2,4移到队尾 → [2,4] → 2出圈 第5轮：4出圈 输出：3 1 5 2 4

4. 算法特点

时间复杂度：O(n×m)，因为每个人出圈需要移动m-1次
空间复杂度：O(n)，队列存储n个元素
优点：直观易懂，代码简洁
适用性：适用于n和m较小的情况（本题限制为≤100）

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

2025 csp-j 复赛真题及答案解析（最新更新）
2025 csp-x(山东) 复赛真题及答案解析（最新更新）
2025 csp-x(河南) 复赛真题及答案解析（最新更新）
2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
2025 csp-x(江西) 复赛真题及答案解析（最新更新）
2025 csp-x(广西) 复赛真题及答案解析（最新更新）
2020 ~ 2024 csp 复赛真题题单及题解
2019 ~ 2022 csp-j 初赛高频考点真题分类解析
2021 ~ 2024 csp-s 初赛高频考点解析
2023 ~ 2024 csp-x (山东)初赛真题及答案解析
2024 csp-j 初赛真题及答案解析
2025 csp-j 初赛真题及答案解析（最新更新）
2025 csp-s 初赛真题及答案解析（最新更新）
2025 csp-x (山东)初赛真题及答案解析(最新更新)
2025 csp-x (江西)初赛真题及答案解析(最新更新)
2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、前缀和、差分、深搜、广搜、DP专题、树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

csp信奥赛C++标准模板库STL案例应用14