P4852 约瑟夫问题2（基础）

解题思路

第一步，理解题意。 n 个人围成一圈，编号从 1 到 n，第 i 个人有一个名字。从第 1 个人开始报数，报到 m 的那个人出圈，然后由下一个人重新从 1 开始报数。一直重复，直到所有人都出圈。我们要按出圈的先后顺序，输出每个人的编号和名字。

第二步，类比游戏。 这就是"丢手绢"游戏：小朋友们围成一圈，从某个小朋友开始往下数，数到 m 的那个小朋友就要走出圈外。数到 m 之后，从下一个小朋友重新数 1、2、3……

第三步，用数组模拟。 开数组 a，a[i]=0 表示第 i 个人还在圈里，a[i]=1 表示已经出圈。再用三个变量：pos 记录当前报到谁，cnt 记录报数报到几，out 记录已经出圈几个人。名字用二维字符数组 name[i] 存第 i 个人的名字，长度不超过 30。

第四步，循环报数。 pos 每次向后走一格，走到 n 之后用 pos = pos % n + 1 回到 1，实现"围成一圈"。如果这个人还在圈里，cnt 加 1；当 cnt 等于 m 时，这个人出圈，输出编号和名字，out 加 1，cnt 重新变成 0。重复到 out 等于 n。

第五步，边界情况。 m 可能比 n 大（比如 n=2、m=1000），程序不关心 m 和 n 的大小关系，只要不断转圈数到 m 为止即可。报数时已经出圈的人要跳过，不能算数。举个例子：n=5、m=3 时，3 号 Xiaotong 先出圈，然后从 4 号开始报数，接下来出圈的是 1 号 Xiaocheng、5 号 Xiaolu、2 号 Xiaomei、4 号 Daxiong，和样例一致。

参考代码

// 约瑟夫问题2：n个人围圈报数，数到m出圈，输出编号和名字
#include <iostream>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    char name[1005][35];      // 名字
    for (int i = 1; i <= n; i++) cin >> name[i];
    int a[1005] = {0};        // a[i]=0 表示还没出圈
    int out = 0;              // 已出圈人数
    int pos = 0;              // 当前报数位置
    int cnt = 0;              // 报数
    while (out < n) {
        pos = pos % n + 1;    // 循环移动
        if (a[pos] == 0) {
            cnt++;
            if (cnt == m) {   // 数到m，出圈
                a[pos] = 1;
                cout << pos << ' ' << name[pos] << endl;
                out++;
                cnt = 0;
            }
        }
    }
    return 0;
}

复杂度分析

时间复杂度：每出圈一个人，最多需要转完一整圈 n 个位置，共有 n 个人出圈，所以最坏是 O(n·m) 量级。n、m 最大都是 1000，最多约 1 百万次操作，非常快。

空间复杂度：名字数组是 n×35 个字符，加上标记数组，是 O(n)。