猴子选大王

GitHub跳转原题关系图返回列表

把圆圈按报数方向摊成队列:报数就是队首出队,没数到排回队尾,数到就淘汰,新队首即下一轮起点。

OJ: roj

题目 ID: 1418

难度:普及

标签:模拟队列约瑟夫问题python

创建: 2026-10-07 15:24

更新: 2026-10-07 15:24

形式化题目

NN 只猴子编号 1,2,…,N1, 2, \dots, N 围成一圈,第 ii 只猴子带一个步数 XiX_i。 一开始"当前猴子"是 11 号;只要圈里还剩多于一只猴子,就重复下面的过程:

  1. 从当前猴子开始数数,当前猴子自己算第 11 个,沿圈向后数到第 X当前X_{\text{当前}} 只仍在圈内的猴子,这只猴子出队;
  2. 出队猴子的下一位(它的后继)成为新的"当前猴子"。

求最后剩下的猴子编号。约束:1⩽N⩽1061 \leqslant N \leqslant 10^6,1⩽Xi⩽1001 \leqslant X_i \leqslant 100。

有两处容易读错:数数时只数还在圈里的猴子(已经出队的猴子不再占位置),并且每轮数到几由本轮的起点猴子决定,而不是由出队的那只决定。

样例推演

以样例 N=5N = 5、X=(1,2,3,4,5)X = (1, 2, 3, 4, 5) 为例。下表"队列"一列就是下面解法里的队列(队首在左,队尾的下一位绕回队首):

轮次 本轮起点 要数到 出队后又排回队尾 本轮淘汰 淘汰后的队列
1 1 X1=1X_1 = 1 — 1 2,3,4,52,3,4,5
2 2 X2=2X_2 = 2 2 3 4,5,24,5,2
3 4 X4=4X_4 = 4 4, 5, 2 4 5,25,2
4 5 X5=5X_5 = 5 5, 2, 5, 2 5 22

出队顺序 1,3,4,51, 3, 4, 5 与题面一致,最后剩下 22 号,输出 22。 第 4 轮值得注意:数到第 55 只时已经在 5,25, 2 之间来回走了两遍,说明报数不限制圈数。

正解

思路

朴素做法卡在哪。 最直接的做法是照题意模拟:用数组存下圈,每轮从起点开始数到第 XiX_i 只还在圈里的猴子并把它删掉。麻烦集中在两点:

  • 怎么"删掉":数组删除要搬移元素,NN 次删除就是 O(N2)O(N^2);换成链表可以 O(1)O(1) 摘除,但要为每只猴子维护前后指针。
  • 怎么"数到第 XiX_i 只还在圈里的猴子":必须跳过已经出队的猴子,不能按数组下标直接走。

更关键的是,总报数次数是躲不掉的:每一轮至少要把 X起点X_{\text{起点}} 只猴子数一遍,N−1N-1 轮合起来就是 ∑Xi⩽100(N−1)≈108\sum X_i \leqslant 100(N-1) \approx 10^8 次。题目把 XiX_i 限制在 100100,正是为了让这个量级可以接受。 所以我们要做的不是"减少数数次数",而是找一个前进 O(1)O(1)、又自动跳过已出队猴子的结构。

把圆圈摊成队列。 关键观察:如果把所有还在圈里的猴子,按"从当前起点出发的报数方向"排成一条队列,那么

  • 队首就是本轮起点(正要报数的那只猴子);
  • "报一次数"就是把队首取出来看一眼;
  • 如果它不是本轮要被淘汰的,把它接到队尾——它成了本轮最后报数的那只,下一轮又从队首开始数,正好等价于"在圈上向后走一只";
  • 如果它正是要被淘汰的,直接丢掉它,此时新的队首恰好是它的后继,也就是下一轮的起点。

于是"沿圈走一只"变成了"队首出队、队尾入队"两个 O(1)O(1) 操作,已经出队的猴子早就被丢掉了,根本不会被数到。队列里存的永远只有还在圈里的猴子,上面那两个麻烦同时消失:不需要手写指针,也不需要"跳过空位"。

每轮数到几。 次数由本轮起点决定,所以一开始 target = X_1;每当淘汰一只猴子,新的队首就是下一轮的起点,把 target 换成它的 XX 即可。

为什么循环数组就够。 每轮报数要么让队列长度不变(出队后又入队),要么减一(淘汰),所以队列里最多同时有 NN 只猴子。用一个容量 N+1N+1 的循环数组(head、tail 取模回绕)就够了,不必动态扩容;在 10810^8 次操作下,定长数组的常数也比 STL 容器更小。

边界。 N=1N = 1 时圈里本来就只有一只猴子,一轮都不用数,直接输出 11(代码里 while (alive_cnt > 1) 保证了这一点)。

代码

Python 版:

python
#!/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-07 15:15
# update_at: 2026-10-07 15:15

import sys
from collections import deque


def last_monkey(step: list[int]) -> int:
    """把圆圈摊成队列模拟报数,返回最后剩下的猴子编号;step[i] 是 i 号猴子的 Xi。"""
    circle = deque(range(1, len(step)))  # 队首是本轮起点,队尾的下一位绕回队首
    target = step[1]                     # 本轮要数到的次数,由起点(队首)的 Xi 决定
    counted = 0                          # 本轮已经数了几只猴子
    while len(circle) > 1:
        counted += 1
        monkey = circle.popleft()
        if counted == target:            # 正好数到目标:这只猴子淘汰,不回队尾
            counted = 0
            target = step[circle[0]]     # 下一轮从它的下一位开始,次数换成新队首的 Xi
        else:
            circle.append(monkey)        # 没数到:排回队尾等下一轮
    return circle[0]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    step = [0] + [next(data) for _ in range(n)]  # step[i] = Xi,下标从 1 开始对应猴子编号
    print(last_monkey(step))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * 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-07 15:15
 * update_at: 2026-10-07 15:15
 */
// main.cpp:猴子选大王。把圆圈按报数方向摊成一条队列:报数 = 队首出队,
// 没数到就排回队尾,数到就淘汰;淘汰后新的队首正好是下一轮的起点。
#include <cstdio>

typedef long long ll;

const int MAXN = 1000000 + 5;

ll n;              // 猴子总数
int x[MAXN];       // x[i]:i 号猴子作为本轮起点时要数到的次数 Xi(Xi <= 100,用 int 省内存)
int circle[MAXN];  // 循环队列:按报数方向存还在圈里的猴子编号,队首是本轮起点(编号 <= 1e6)
int head, tail;    // 队首、队尾下标
int alive_cnt;     // 队列里的猴子数,也就是圈里还剩几只

// 把猴子 v 接到队尾。队列里最多同时有 N 只猴子,容量 MAXN 的循环数组足够。
void push_monkey(int v) {
    circle[tail] = v;
    if (++tail == MAXN) tail = 0;
    ++alive_cnt;
}

// 队首猴子出队,返回它的编号。
int pop_monkey() {
    int v = circle[head];
    if (++head == MAXN) head = 0;
    --alive_cnt;
    return v;
}

// 看一眼队首猴子的编号,不出队。
int front_monkey() {
    return circle[head];
}

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &x[i]);
        push_monkey(i);  // 1..n 依次入队,队首就是 1 号猴子
    }

    ll target = x[1];  // 本轮要数到的次数,由本轮起点(队首)的 Xi 决定
    ll counted = 0;    // 本轮已经数了几只猴子

    while (alive_cnt > 1) {       // 圈里只剩一只猴子时它就是大王,n = 1 时一轮都不数
        ++counted;
        int cur = pop_monkey();   // 队首猴子报数后先出队
        if (counted == target) {  // 正好数到本轮目标:这只猴子被淘汰,不再回到圈里
            counted = 0;
            target = x[front_monkey()];  // 下一轮从它下一位开始,次数换成新队首的 Xi
        } else {
            push_monkey(cur);     // 没数到:排回队尾,等下一轮继续数
        }
    }

    printf("%d\n", front_monkey());  // 最后剩下的猴子就是大王
    return 0;
}

复杂度

  • 时间:第 rr 轮要报数 X起点⩽100X_{\text{起点}} \leqslant 100 次,一共淘汰 N−1N-1 只猴子,所以总操作次数为 ∑Xi⩽100(N−1)\sum X_i \leqslant 100(N-1),即 O(∑Xi)⩽O(100N)O(\sum X_i) \leqslant O(100N);N=106N = 10^6 时约 10810^8 次 O(1)O(1) 的出队/入队(实测顶格数据 N=106N = 10^6、Xi≡100X_i \equiv 100 约 0.150.15 s,限制 500500 ms)。
  • 空间:O(N)O(N)。x[] 与循环队列 circle[] 各约 NN 个 int,N=106N = 10^6 时合计约 8 MB(限制 64 MB)。

总结

这道题就是"步长会变的约瑟夫环":固定的 mm 换成了"由当前起点猴子的 XX 决定"。队列模拟之所以好用,是因为它把"圈上的顺序"和"报数的进度"编码进了同一个结构——队首是当前起点,队尾的下一位就是绕回队首,出队再入队一次就同时完成了"向前走一只"和"跳过已出队的猴子"。

写代码时抓住两个不变量就不会错:

  1. 队列里只有还在圈里的猴子,且它们的排列顺序就是圈上的顺序;
  2. 队首永远是本轮的起点,所以 target 只在"淘汰发生"时更新成新队首的 XX。

复杂度的上界 O(100N)O(100N) 依赖 Xi⩽100X_i \leqslant 100。如果步长可以很大(比如到 10910^9),∑Xi\sum X_i 会爆掉, 那时就要换成用树状数组维护"第 kk 只还在圈里的猴子",把每轮定位从 O(Xi)O(X_i) 压到 O(log⁡N)O(\log N)。