蓝桥杯模拟赛:报数游戏(vector解决约瑟夫环)

简介: 题:报数游戏有 n ( 1< n n >> m; vectorvec(n); for(int i = 0; i < n; i++) { vec[i] = i+1; } int x = 0; while(1) { x = (x+m-1) % vec.

题:报数游戏

有 n ( 1< n<10000)个小朋友站成一个圆圈。
选定一个小朋友为1号,从他(她)开始顺时针编号:1,2,3,4,…

游戏开始! 从1号小朋友起,顺时针报数,从1报起。
即:1号小朋友报1,2号小朋友报2,3号小朋友报3, ….

游戏规定,报到数字 m(1 < m <100) 的小朋友立即退出报数圈。
在他(她)的顺时针方向的下一个小朋友(如果有的话)开始重新从1报数…
游戏这样一直进行下去,直到圈中只剩下一个小朋友。

求最后剩下的小朋友的编号。

输入:两个整数,n 和 m, 用空格分开。含义如上。

输出:一个整数,表示最后剩下的小朋友的编号。

比如:
输入:
15 3
程序应该输出:
5

再比如:
输入:
7 4
程序应该输出:
2

资源约定:
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms

分析:
删除报到数的”孩子”直到容器大小等于1

#include <iostream>
#include <vector>
using namespace std;
int main()
{   
    int n, m;   //n孩子数 m报数 
    cin >> n >> m;
    vector<int>vec(n);
    for(int i = 0; i < n; i++) {
        vec[i] = i+1;
    }
    int x = 0;
    while(1) {
        x = (x+m-1) % vec.size();
        vec.erase(vec.begin()+x);   //删除下标为x的"孩子" 
        if(vec.size() == 1) {
            cout <<vec[0];  //剩下的最后一个"孩子" 
            break;
        }
    }   
    return 0;
 }
目录
相关文章
|
机器学习/深度学习 Python
【蓝桥杯】约瑟夫环--python
【蓝桥杯】约瑟夫环--python
127 0
|
3月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1005 数字游戏
57 0
|
3月前
|
Java C语言 C++
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-1000 kAc给糖果你吃
41 0
|
3月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-999 数的潜能
40 0
|
3月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-997 粘木棍
48 0
|
3月前
|
机器学习/深度学习 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-996 车的放置
43 0
|
3月前
|
人工智能 算法 Java
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-992 士兵杀敌(二)
27 1
|
3月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-986 藏匿的刺客
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-986 藏匿的刺客
43 0
|
3月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-985 幸运的店家
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-985 幸运的店家
46 0
|
3月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-983 最大获利
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-983 最大获利
43 0