问题介绍
约瑟夫问题有很多经典例题,例如猴子选王、丢手绢。在算法学习过程中,这是大部分人都会遇到的一类问题。然而大家往往只知道 $\mathcal{O}(n \times m)$ 的模拟解法。
首先给出该问题的情景:$n$ 个人围成一圈,编号为 $1$ 到 $n$。从 $1$ 号最先从 $1$ 开始报数,每次报到 $m$ 的人出圈,下一个人重新从 $1$ 开始报数,直到剩下最后一人为止。
解法介绍
其中影响到一个人在出圈顺序中的位置 $id$ 的有三个关键参量:他的编号 $i$ 、人数 $n$ 以及出圈间歇 $m$。
在某些情况下,部分参量并不起作用。如 $m|i$ 时, $i$ 对 $id$ 无影响; $m = 1$ 时, $n$ 对 $id$ 无影响。在部分题目中这可能成为解题的关键。
该类问题有两种问法,分别是:
询问约瑟夫排列(即出圈顺序)
询问第 $k$ 出圈(第 $n$ 出圈为获胜者)
询问约瑟夫排列
一般情况
时间复杂度 $\mathcal{O}(n \log n)$。
这样考虑问题:假定当前出圈的人编号为当前第 $k$ 小,此人出圈后圈内还有 $n$ 人,那么下一个出圈的人为圈内编号第 $(k-1+m-1)\bmod n + 1$ 小。
那么只需要一个数据结构,满足能够单点修改,并查询区间第 $k$ 小的:权值树状数组。
1 |
|
当然也可以使用顺序统计树
询问第 $k$ 出圈
时间复杂度 $\mathcal{O}(k)$
令 $f(n,m,k)$ 表示第 $k$ 出圈人。
有公式:
代码实现如下
1 | int f(int n, int m, int k) { |
当然也有非递归的写法
1 | int f(int n, int m, int k) { |
时间复杂度 $\mathcal{O}(\log_{\frac{m}{m - 1}}n)$
当 $n>>m$ 时,每次从 $1$ 到 $n$ 的一个循环中,有 $\lfloor \frac{n}{m} \rfloor \times m$ 人报数,其中 $\lfloor \frac{n}{m} \rfloor$ 人出圈。
参考前面时间复杂度 $\mathcal{O}(k)$ 的式子,可以发现在此过程中有许多取模操作是无作用的。
于是我们可以合并一些操作,使得部分加法合并为乘法。
有公式
式中 $c$ 表示从当前的 $n$ 一直变化到到 $c$ 的期间内取模都无作用的最大的 $c$。
代码如下
1 | int f(int n, int m, int k) { |
时间复杂度 $\mathcal{O}(\frac{mk}{n})$
易知第 $k$ 出圈人为第 $k \times m$ 报数人,以此为基础进行推导。
首先明确几个概念:
位置编号:从 $1$ 开始编号到 $n$,表示在圈内的初始编号为 $k$。
报数编号:从 $1$ 开始编号到 $n \times m$,表示第 $k$ 次报数。
报数:从 $1$ 开始编号到 $m$,表示某人所报的某个数。
首先取一个报数编号 $p$,对应位置编号 $id$。可以用该式来表示:$p = a \times m + b$ ($0 \leq a < n$, $1 \leq b \leq m$)。实际含义是:在第 $a$ 轮报数结束后,报数为 $b$。
那么容易推出以下信息:
此时圈内所剩人员数量为 $n - a$
若此人报数 $b = m$,则此人出局。否则圈内剩余的人将会恰好各报一次数,然后此人会再一次报数。
假设此人未出局,那么 $b < m$。
设此人下一次报数编号为 $q$,易知 $q = p + n - a = a \times (m - 1) + b + n$。
那么可以推导:$a = \dfrac{q - n - b}{m-1} = \lfloor \dfrac{q - n - 1}{m - 1} \rfloor$。
所以有:$p = q - n + a = q - n - \lfloor \dfrac{q - n - 1}{m - 1} \rfloor = \lfloor \dfrac{(q - n - 1) \times m}{m - 1} \rfloor + 1$
这样就完成了后继公式到前驱公式的变化,如此不断迭代,直到得到他是第 $k$ 报数人为止。
有公式:
代码实现如下:
1 | int g(int n, int m, int x) { |
注意到该函数可以非递归实现,给出优化后的代码
1 | int f(int n, int m, int k) { |