选小寿星

题目描述

$m$ 名学生围成一个圈，编号 $1 \sim m$ ，从 1 号开始沿圈连续报数 $1, 2, 3, \dots$ ：报到 $n$ 的人出局，他的下一位从 1 重新报数，直到只剩 1 人。特殊规则：女生（标记为 0）有 2 次机会，第 1 次数到 $n$ 不出局，第 2 次才出局；男生数中即出局。

输入第一行为 $m$ （ $m \leqslant 20$ ），第二行为 $m$ 个整数（1 表示男生，0 表示女生），第三行为 $n$ （ $1 \leqslant n \leqslant 9$ ）；输出最后留下学生的编号。样例：输入 $m=5$ ，性别 1 1 0 0 1， $n=3$ ，输出 5；又如 $m=3$ ，性别 1 0 1， $n=2$ ，输出 2。

思路

用循环队列模拟报数：圈内的人按报数顺序入队，队首永远是下一个报数的人，每人的剩余机会 chances[i] 为男 1、女 2。每步队首出队报数：没数到 $n$ 就回队尾；数到 $n$ 则报数计数清零并消耗一次机会，还有剩余就回队尾，否则出局不再入队。女生"2 次机会"被完全吸收进 chances 初值，总步数 $O(mn)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 01:38
# update_at: 2026-10-01 01:38

from collections import deque
from collections.abc import Iterator
import sys

MAX_CHANCE = 2  # 女生共 2 次机会，第二次数到 n 才出局


def survive(n: int, chances: list[int]) -> int:
    """按 chances 里的剩余机会逐个出局，返回最后留下的人（下标从 1 起）。

    每轮连续出局后，报数接力交到下一个未出局的人手上。
    """
    ring = deque(range(len(chances)))  # 存下标，人数最多 20，不用公式跳位
    counter = 0                        # 当前这一棒已经报到的数字
    while len(ring) > 1:
        index = ring.popleft()
        counter += 1
        if counter < n:
            ring.append(index)         # 没数到 n，回到队尾继续
            continue
        chances[index] -= 1            # 数到 n：用掉一次机会
        counter = 0                    # 下一个人从 1 重新报数
        if chances[index] > 0:
            ring.append(index)         # 还有机会，站在队尾等下一轮报数
    return ring[0] + 1


def read_people(tokens: Iterator[str]) -> list[int]:
    """读入 m 与性别序列，换算成每个人的剩余机会：女生 2 次，男生 1 次。"""
    m = int(next(tokens))
    return [MAX_CHANCE if next(tokens) == b'0' else 1 for _ in range(m)]


def solve() -> None:
    tokens = iter(sys.stdin.buffer.read().split())
    chances = read_people(tokens)
    n = int(next(tokens))
    print(survive(n, chances))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:49
 * update_at: 2026-10-06 01:49
 */

#include <cstdio>
#include <queue>
using namespace std;

typedef long long ll;

const ll MAXN = 25;

ll m, n;               // m 个人围成圈，报数到 n 出局
ll sex[MAXN];          // sex[i] = 1 表示男生，0 表示女生
ll chances[MAXN];      // chances[i] 表示第 i 个人剩余的"数中机会"，男 1 女 2

// 循环队列模拟报数：队首永远是下一个报数的人
void solve() {
    queue<ll> q;
    for (ll i = 1; i <= m; ++i)
        q.push(i);

    ll counter = 0;    // 当前这一棒已经报到的数字
    while (q.size() > 1) {
        ll p = q.front();
        q.pop();
        counter++;
        if (counter < n) {
            q.push(p);         // 没数到 n，回到队尾继续报数
            continue;
        }
        counter = 0;           // 数到 n：下一个人从 1 重新报数
        chances[p]--;          // 用掉一次机会
        if (chances[p] > 0)
            q.push(p);         // 女生第 1 次数中不出局，站回队尾
        // 机会用完则不再入队，即出局
    }
    printf("%lld\n", q.front());
}

int main() {
    scanf("%lld", &m);
    for (ll i = 1; i <= m; ++i) {
        scanf("%lld", &sex[i]);
        chances[i] = (sex[i] == 0) ? 2 : 1; // 女生 2 次机会，男生 1 次
    }
    scanf("%lld", &n);
    solve();
    return 0;
}

目录

题目描述

思路

参考代码