P4846 猴子选大王（基础）

解题思路

**第一步，把猴子排成一队。**n只猴子按编号1到n排好队，我们用循环队列来模拟。队头h指向下一只要报数的猴子，队尾t用来放“站到队伍最右侧”的猴子。

**第二步，理解报数规则。**每只猴子依次报数，从1报到m：报到m的那只猴子出列（被淘汰）；报其他数字的猴子不离开，而是立即站到队伍最右边，等着下一轮重新报数。就这样一直进行，直到全部猴子出列，最后出列的那只就是猴王。

**第三步，模拟的具体写法。**用cnt记录当前该报的数字。每次从队头取出一只猴子：如果cnt等于m，说明它报到m了，把它淘汰，同时记录一下它是“最后出列”的猴子，cnt重置为1；否则cnt加1，把这只猴子放回队尾。一直做，直到剩余猴子数为0，最后记录的那个编号就是猴王。

**第四步，为什么必须用循环队列？**如果m很大，比如m=299，那么报数会围着队伍绕很多很多圈，同一只猴子会被一遍又一遍放回队尾，队尾下标会一直往后涨。如果只开一个固定的大数组而不取模，就会越界崩溃。所以队头和队尾都要对数组长度取模，让位置循环复用，这就是“循环队列”。

**举例子验证。**输入 5 3：第一圈3号报到3出列，第二圈1号出列，第三圈5号出列，第四圈2号出列，最后4号出列，4号就是猴王，和样例一致。

参考代码

// P4846 猴子选大王：循环队列报数1~m，报到m的出列，其余回队尾
#include <iostream>
#include <cstdio>
using namespace std;
int n, m;
int q[1005];
int h, t;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {   // 猴子按编号入队
        q[t] = i;
        t = (t + 1) % 1005;
    }
    int cnt = 1, last = 0, rest = n;
    while (rest > 0) {
        int cur = q[h];
        h = (h + 1) % 1005;   // 队首出队
        if (cnt == m) {       // 报到m出列
            cnt = 1;
            rest--;
            last = cur;
        } else {              // 其余站到队尾
            cnt++;
            q[t] = cur;
            t = (t + 1) % 1005;
        }
    }
    printf("%d\n", last);  // 最后出列的就是猴王
    return 0;
}

复杂度分析

每只猴子每次经过队头都要参与报数，每淘汰一只猴子最多要绕圈子报m个数，总共淘汰n只，所以最坏时间是O(n·m)。n和m都小于300，最坏也就九万步，非常快。空间上循环队列只需要能装下n只猴子，约O(n)。