1493围圈报数（队列）

题目描述

有ｎ个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为1，2，…，n，打印出列的顺序。

输入

n和m。

输出

出列的顺序。

样例输入：

4 17

样例输出 ：

1 3 4 2

解决方案：

一.使用队列

实现思路：

建立队列。队列长度与圆圈人数相同。队列按顺序赋序号初值。

对每个人的编号，都要做一个标记。这个标记可以用 0 和 1 。

0表示还没有出列，1表示已经出列了。

从队首查询队列。取队列的第一个元素。如果这个元素的标记是0的话，计数一次。

如果是1的话，直接弹出。

对标记为0的情况进行更细致的讨论：

如果当前计数不是出列数的倍数，将队首元素追加在队尾，同时弹出队首元素；

如果当前计数是出列数的倍数，将队首元素输出、追加在队尾，并将元素编号对应的标记赋值为1，同时弹出队首元素。

此处不用考虑某个编号是否已经出列、用不用追加在队尾，直接追加在队尾就可以。因为对任意一个队首元素，会先进行标记是否为0的判断。如果标记为0则做进一步处理，如果为1则直接弹出。

判断查询这个循环终止的条件：每次输出一个数，另一个计数变量自加一下。当这个计数变量与总人数正好相等时，说明所有人已经全部输出。循环结束。

代码部分：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5;
int a[N];
int main()
{int n, m;cin >> n >> m;int cnt = 0;//计数int cntsum = 0;//已经出队的人数计数queue<int>q;//定义队列for (int i = 1; i <= n; i++)q.push(i);//队列赋值int head;//队首元素的定义，方便书写while (!q.empty()){if (cntsum == n)break;//如果已经出队的人数与总人数相等，终止循环head = q.front();//队首元素每次赋初值if (a[head] == 0)//如果还未曾出队，执行更精确的操作{cnt++;//如果还未曾出队，计数。if (cnt % m != 0)//如果当前计数不是出队数的倍数{q.push(head);//将队首元素追加到队尾}else if (cnt % m == 0)//如果当前计数是出队数的倍数{cout << head << " ";//输出队首元素q.push(head);//将队首元素追加到队尾cnt = 0;//计数重新开始a[head] = 1;//编号已经出队，做标记cntsum++;//已经出队的人数，计数。}}//如果出队了，不执行if语句体，直接弹出//如果没出队，执行完更精确的操作之后，也要弹出队首元素//综上，不管编号是否出队，都需要弹出队首元素。q.pop();}return 0;
}