P4839 选标兵（基础）

解题思路

第一步，理解报数出列的规则。 有 M 个人，编号分别是1到M，他们围成一圈站好。从编号1的人开始，顺时针依次报数1、2、3……报到数字 N 的那个人出列；然后从出列那个人的下一个人开始，又从1重新报数。这样一直循环，直到所有人都出列为止。题目要我们按出列的先后顺序，把编号一行一行输出来。

第二步，用数组模拟圆圈。 围成一圈站人，可以用数组 a 表示，a[i]=1 表示编号 i 的人还在圈里，a[i]=0 表示他已经出列了。用变量 pos 记录"目前数到哪个人"，顺时针移动的时候 pos 加1，如果 pos 超过了 M，就把它变成1，这样队伍就首尾相接成了一圈。

第三步，数到 N 的人出列。 每次从当前 pos 的位置开始数数：让 pos 一步步往前移动，但移动的时候只看还在圈里的人——只有 a[pos] 等于1才算是数了一步，等于0（已经出列）就直接跳过。数满 N 步之后停下来，停在的那个人就是要出列的，把 a[pos] 改成0、人数 left 减1，并输出 pos。然后开始下一轮报数，此时 pos 正好停在这个出列的人身上，下一轮第一下就会走到他的下一个人，完全符合"从下一个人重新报数"。

第四步，注意数据范围。 M 在8到15之间，人数很少；但 N 可能很大，最大到32767。数 N 步其实就是在最多15个人之间转圈，最多转三千多圈，每圈15步，总共不到50万次操作，程序跑得非常快。

第五步，拿样例验证。 M=9、N=6：从1开始数，1、2、3、4、5、6，6出列；从7开始数，7、8、9、1、2、3，3出列；从4开始数，4、5、7、8、9、1，1出列……一直数下去，出列顺序是 6 3 1 9 2 5 4 8 7，和样例一致。

参考代码

// 选标兵：约瑟夫问题，M人围成一圈报数，数到N出列，输出全部出列顺序
#include <iostream>
using namespace std;

int main() {
    int a[16];   // a[i]=1表示第i个人还在圈里
    int m, n, i;
    cin >> m >> n;
    for (i = 1; i <= m; i++) a[i] = 1;
    int left = m, pos = 0;
    while (left > 0) {
        int step = n;   // 报数报到n的人出列
        while (step > 0) {
            pos++;               // 顺时针走到下一个人
            if (pos > m) pos = 1;
            if (a[pos]) step--;  // 只数还在圈里的人
        }
        a[pos] = 0;              // 该人出列
        left--;
        cout << pos << endl;
    }
    return 0;
}

复杂度分析

M 最大为15，每个人出列时都要数 N 步，N 最大为32767，所以总操作次数大约是 M×N，最多不到50万次，时间复杂度 O(M×N)，运行速度很快。空间上只需要一个长度为16的数组记录每个人是否还在圈里，空间复杂度是 O(M)。