把圆圈按报数方向摊成队列:报数就是队首出队,没数到排回队尾,数到就淘汰,新队首即下一轮起点。
OJ: roj
题目 ID: 1418
难度:普及
标签:模拟队列约瑟夫问题python
创建: 2026-10-07 15:24
更新: 2026-10-07 15:24
形式化题目
- 从当前猴子开始数数,当前猴子自己算第
个,沿圈向后数到第 只仍在圈内的猴子,这只猴子出队; - 出队猴子的下一位(它的后继)成为新的"当前猴子"。
求最后剩下的猴子编号。约束:
有两处容易读错:数数时只数还在圈里的猴子(已经出队的猴子不再占位置),并且每轮数到几由本轮的起点猴子决定,而不是由出队的那只决定。
样例推演
以样例
| 轮次 | 本轮起点 | 要数到 | 出队后又排回队尾 | 本轮淘汰 | 淘汰后的队列 |
|---|---|---|---|---|---|
| 1 | 1 | — | 1 | ||
| 2 | 2 | 2 | 3 | ||
| 3 | 4 | 4, 5, 2 | 4 | ||
| 4 | 5 | 5, 2, 5, 2 | 5 |
出队顺序
正解
思路
朴素做法卡在哪。 最直接的做法是照题意模拟:用数组存下圈,每轮从起点开始数到第
- 怎么"删掉":数组删除要搬移元素,
次删除就是 ;换成链表可以 摘除,但要为每只猴子维护前后指针。 - 怎么"数到第
只还在圈里的猴子":必须跳过已经出队的猴子,不能按数组下标直接走。
更关键的是,总报数次数是躲不掉的:每一轮至少要把
把圆圈摊成队列。 关键观察:如果把所有还在圈里的猴子,按"从当前起点出发的报数方向"排成一条队列,那么
- 队首就是本轮起点(正要报数的那只猴子);
- "报一次数"就是把队首取出来看一眼;
- 如果它不是本轮要被淘汰的,把它接到队尾——它成了本轮最后报数的那只,下一轮又从队首开始数,正好等价于"在圈上向后走一只";
- 如果它正是要被淘汰的,直接丢掉它,此时新的队首恰好是它的后继,也就是下一轮的起点。
于是"沿圈走一只"变成了"队首出队、队尾入队"两个
每轮数到几。 次数由本轮起点决定,所以一开始 target = X_1;每当淘汰一只猴子,新的队首就是下一轮的起点,把 target 换成它的
为什么循环数组就够。 每轮报数要么让队列长度不变(出队后又入队),要么减一(淘汰),所以队列里最多同时有 head、tail 取模回绕)就够了,不必动态扩容;在
边界。 while (alive_cnt > 1) 保证了这一点)。
代码
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++ 版(同一算法):
/**
* 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;
}复杂度
- 时间:第
轮要报数 次,一共淘汰 只猴子,所以总操作次数为 ,即 ; 时约 次 的出队/入队(实测顶格数据 、 约 s,限制 ms)。 - 空间:
。 x[]与循环队列circle[]各约个 int,时合计约 8 MB(限制 64 MB)。
总结
这道题就是"步长会变的约瑟夫环":固定的
写代码时抓住两个不变量就不会错:
- 队列里只有还在圈里的猴子,且它们的排列顺序就是圈上的顺序;
- 队首永远是本轮的起点,所以
target只在"淘汰发生"时更新成新队首的。
复杂度的上界