P4841 选领诵（提高）

解题思路

**第一步，理解这个报数游戏。**同学们围成一圈，从第1个同学开始数数，从1数到m，数到m的那个同学就要处理一下：男生数到m直接出局；女生有2次机会，第一次数到m只是“警告”，记下来，第二次数到m才出局。处理完以后，从下一位同学重新开始数。

**第二步，用什么数据结构？**题目要求用循环队列。我们用数组模拟一个“圆环”：用 pos 记录当前从谁开始报数，用 alive 数组记录每个人还在不在场，用 cnts 数组记录每个女生已经“警告”过几次。报数时一圈一圈往前走，遇到已经出局的人就直接跳过。

**第三步，按步骤模拟。**每一轮从 pos 开始，让在场的人报数，报到第m个人的时候停下来，这个人就是本轮的“倒霉蛋”。如果他是男生，直接标记出局；如果是女生，把他的警告次数加1，警告满2次才出局。无论出局还是警告，下一轮都从下一位开始。

**第四步，注意边界情况。**m可以是1，那样每个人报的数都是1，马上就到m；女生出局需要2次，所以哪怕m=1，女生也要等两轮才出局。还要注意报数时跳过已出局的人，不然会数到空位。

**举例子验证。**比如 n=5，性别是 男男男女女男，m=3。第一轮报到3号女生，警告一次；第二轮报到1号男生，男生出局；第三轮报到4号女生，警告一次；第四轮3号女生警告满2次出局；第五轮2号男生出局；第六轮4号女生警告满2次出局；最后只剩5号男生，他数到m后出局，5号就是领诵，和样例一致。

参考代码

// P4841 选领诵：循环报数淘汰，男生1次出局，女生有2次机会(第2次数到m才出局)
#include <iostream>
#include <cstdio>
using namespace std;
int n, m;
int sex[25];    // 1男 0女
int cnts[25];   // 被数到m的次数
int alive[25];  // 是否在场
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &sex[i]);
    scanf("%d", &m);
    for (int i = 1; i <= n; i++) alive[i] = 1;
    int rest = n;   // 在场人数
    int pos = 1;    // 从第pos位开始报数
    while (rest > 1) {
        int c = 0;
        while (c < m) {  // 报数1~m
            if (alive[pos]) c++;
            if (c == m) break;
            pos++;
            if (pos > n) pos = 1;
        }
        if (sex[pos] == 1) {  // 男生出局
            alive[pos] = 0;
            rest--;
        } else {              // 女生：第2次数到m才出局
            cnts[pos]++;
            if (cnts[pos] >= 2) {
                alive[pos] = 0;
                rest--;
            }
        }
        pos++;  // 从下一位重新报数
        if (pos > n) pos = 1;
        while (rest > 1 && !alive[pos]) {  // 跳过已出局的人
            pos++;
            if (pos > n) pos = 1;
        }
    }
    for (int i = 1; i <= n; i++)
        if (alive[i]) printf("%d\n", i);
    return 0;
}

复杂度分析

每淘汰一个人，最坏要把一圈同学都数一遍，人数是n，所以一次淘汰约O(n)步。总共有n-1个人要被淘汰（剩下最后一个当领诵），因此总时间是O(n²·m)。不过题目说n<20，这个规模非常小，即使最坏情况也只要几百步，瞬间就能算完。空间上只用了3个长度n的小数组，是O(n)。