P4837 选拔猴王（入门）

解题思路

第一步，理解选大王的过程。 有 N 只猴子要从头到尾排成一队，从第一只开始依次报数1、2、3。报到3的猴子立刻退出队伍；报到1、2的猴子继续留在队伍里。报完队尾以后，又从队伍最前面接着报，继续1、2、3循环。这样一轮一轮下去，队伍里的人越来越少，最后剩下的那一只猴子就是大王。题目要我们输出大王的编号。

第二步，用队列模拟猴子队伍。 队列正好符合"从头出、从尾进"的特点。我们把猴子按编号1到N依次放进数组 q，用 head 和 tail 两个指针维护队头和队尾。每次从队头取出一只猴子 x，就是执行 x=q[head]，然后 head 加1。

第三步，判断报数决定去留。 用变量 c 记录当前该报到几，它在1、2、3之间循环。取出猴子 x 后：如果 c 等于3，这只猴子报到3，退出队伍，同时把 c 重新变成1；如果 c 是1或2，这只猴子不退出，而是转到队尾继续排队，即 q[tail++]=x，同时 c 加1。这样每处理一只猴子，报数就前进一步。

第四步，什么时候结束。 当队列里只剩一只猴子时（head+1 等于 tail），停止循环，队列里这只猴子就是大王，输出它即可。比如 N=4：1报到1转到队尾，2报到2转到队尾，3报到3退出；4报到1转到队尾，1报到2转到队尾，2报到3退出；4报到1转到队尾，1报到2转到队尾，4报到3退出，最后剩下1，输出1，和样例一致。

第五步，注意数组大小。 因为报到1、2的猴子会反复回到队尾，队列会比一开始长不少，最多需要大约3N个格子。N最大是100，所以数组开400个格子就足够了。

参考代码

// 选拔猴王：约瑟夫问题，1-3循环报数，报到3的退出，求最后留下的猴子
#include <iostream>
using namespace std;

int main() {
    int q[400];
    int n, i;
    cin >> n;
    for (i = 0; i < n; i++) q[i] = i + 1;  // 猴子编号1~n依次入队
    int head = 0, tail = n;
    int c = 1;  // 当前报到的数，1、2、3循环
    while (head + 1 < tail) {   // 至少还剩2只猴子
        int x = q[head++];
        if (c == 3) {           // 报到3的猴子退出
            c = 1;
        } else {                // 报1或2的猴子转到队尾
            q[tail++] = x;
            c++;
        }
    }
    cout << q[head] << endl;    // 最后剩下的猴子就是大王
    return 0;
}

复杂度分析

N 最大为100，每只猴子在队列中进进出出，总共大约3N次操作，所以时间复杂度是 O(N)。空间上数组 q 最多需要3N个格子，空间复杂度是 O(N)。