约瑟夫环问题¶
有n个人围成一个圈，每隔k个人踢掉一个人，问最后留下来的人是几号？《具体数学》
朴素算法（直接模拟）¶
典型以SJTU OJ 4089 约瑟夫环为例，需要注意的是下标从1到n，到了LeetCode 面试题 62 圆圈中最后剩下的数字(下标从0到n-1)。时间复杂度是O(nk)。
问题描述¶
设计并实现一个解决约瑟夫环问题的类Joseph。当需要解决一个n个人间隔为m的约瑟夫环问题，可以构建一个对象**Joseph obj(n, m)**，然后调用**obj.simulate()**输出模拟删除过程。
输入输出描述¶
输入¶
- 输入为两个正整数n和m，空格分隔，分别代表编号长度和间隔长度，编号长度n<=50。
输出¶
- 输出为n个整数，空格分隔。
程序运行示例1¶
Sample Input 1¶
10 4
Sample Output 1¶
5 9 3 8 4 1 10 2 7 6
程序运行示例2¶
Sample Input 2¶
30 11
Sample Output 2¶
12 23 4 16 28 10 24 7 21 6 22 9 27 15 3 26 18 13 8 5 11 17 25 2 30 1 20 14 19 29
注意¶
- 约瑟夫环的**起始编号为1**，编号为**[1, n]**。
- 注意判断数组是否溢出。
- m的值可以大于n。
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;
class Joseph {
private:
int n, m;
public:
Joseph(int n, int m) : n(n), m(m) {}
void simulate() {
vector<bool> used(n, false);
int cnt = 0;
int pos = 0;
while (cnt < n - 1) { //去掉n-1个数字
int step = 0;
while (step < m) {
pos = (pos + 1) % n;
if (!used[pos]) {
++step;
if (step >= m) break;
}
}
used[pos] = true; //删掉一个数字
cout << (pos + 1) << " ";
++cnt;
}
for (int i = 0; i < n; ++i) {
if (!used[i]) {
cout << (i + 1) << endl;
return;
}
}
}
};
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int m, n;
cin >> n >> m;
Joseph obj(n, m);
obj.simulate();
return 0;
}
线段树优化¶
此部分在总结到线段树再回来补充。
典型问题：
线性算法¶
LeetCode 面试题 62 圆圈中最后剩下的数字(下标从0到n-1)。
假设n个人的编号式0,1,2,3,\cdots , n - 1，第一轮肯定删掉的数字是k = (m - 1) \% n ，则剩下的数字是0,1,2,\cdots, k - 1, k + 1, \cdots , n - 10,1,2,\cdots, k - 1, k + 1, \cdots , n - 10,1,2,\cdots, k - 1, k + 1, \cdots , n - 10,1,2,\cdots, k - 1, k + 1, \cdots , n - 1，计算下一个删掉的数字就需要从k+1开始计数，这时候对序列重新排序，变成k + 1, \cdots, n - 1, 0,1,2\cdots , k - 1，这样编号就连续了，问题的规模变成了k - 1，加入对它们的序号做个映射，映射成0,1,2,\cdots n - 2，假设映射后的编号为x，那么映射之前的编号就是(x + k + 1) \% n = (x + m) \% n，注意这里是对n取模，因为无论怎么映射，其原来的序号也不能超过n，可以带入检验。那么通过上面的分析和递推式直到，如果我得到了在剩下的n-1个数最后剩下的数的编号x，那么就可以通过(x + m)\% n得到原始的编号，也就是我们需要的答案。
设J_{n, k}表示规模为n, k的约瑟夫问题的答案，标号从0开始（如果从1开始，只需要最后结果+1即可），有递归式： $$ J_{n, k}=\left(J_{n-1, k}+k\right) \bmod n $$
class Solution {
public:
int lastRemaining(int n, int m) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int res = 0;
for (int i = 1; i <= n; ++i) {
res = (res + m) % i;
}
return res;
}
};
算法的时间复杂度是O(n)。
对数算法¶
但是如果n非常大，比如数据规模达到n \leq 10^{12}，比如HDU 3089，上面的算法就会超时，这种特殊情况下，一般会让k的数值比较小，算法复杂度达到O(k \log n)。
当k远小于n的时候，尽可能在第一圈就去除掉尽可能多的数，第一个去掉的是k - 1，第二个去掉的是2k - 1，依次类推，则第一圈最多去掉[n/k]个，余下n - [n / k]个数，写成序列就是： $$ 0,1,2,\cdots .k-2, k, \cdots, 2k-2, 2k, \cdots 3k - 2 \cdots k[n/k] - 2, k[n/k], \cdots ,n - 2, n-1 $$
去掉[n/k]个数后，接下来就要从k[n/k]开始，那么从k[n/k]到n-1的个数肯定是小于k的，那么调整顺序后是： $$ k[n/k], k[n/k] + 1,\cdots, n-1, 0,1,\cdots k-2, k, \cdots k[n / k] - 2 $$ 按照前面的分析，此时应该建立一个映射，对于从k[n/k]到n-1，仍然符合上面的递推关系： $$ J_{n, k} = (J_{n - n/k, k} + k \times [n/k]) \% n $$ 这里的偏移量很好理解，前面每踢一个数，后面偏移时都要多一个k,因为踢了[n/k]个数，所以要偏移[n/k]k。
那么通过上面分析可知，每经过k个数就需要在偏移量补偿1，按照这个思路写一下标号的映射关系： $$ k[n/k], k[n/k] + 1,\cdots, n-1, 0,1,\cdots k-2, k, \cdots k[n / k] - 2 \ n - n \% k, n - n \% k + 1, \cdots, n - n \% k + (n - k[n/k]) - 1 \ 0,1,2,\cdots, n - k[n/k]-1 $$ 其中第一行和第二行是相等的，第三行是子问题J_{n - n/k, k}的标号。
发现如果J_{n - n/k, k} < n-k\times [n/k]，则J_{n, k} = (J_{n - n / k, k} + k\times[n/k]) \% n；
若J_{n - n/k, k} \geq n-k\times [n/k]，则J_{n, k} = (J_{n - n / k, k} + k\times[n/k] + p) \% n，其中p = (J_{n - n / k, k} - n \% k) / (k - 1)，p表示补偿量，注意一个很重要的隐藏关系： $$ n - n \% k = k[n / k] $$
//HDU 3089
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
long long Josephus(long long n, long long k)
{
if (n == 1) return 0;
if (k == 1) return n - 1;
//k>n时退化成线性算法
if (k > n) return (Josephus(n - 1, k) + k) % n;
//判断补偿量
long long res = Josephus(n - n / k, k);
res -= n % k;
if (res < 0) res += n;
else res += res / (k - 1);
return res;
}
int main()
{
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long n, k;
while (cin >> n >> k) {
cout << (Josephus(n, k) + 1) << endl;
}
return 0;
}
上面的代码和公式有一些变化，其实是一致的，只是改进了计算顺序。首先需要去比较J_{n - n / k, k}和n - k[n/k]的关系，判断对应的原序列编号是否在k[n / k]\cdots n-1内。如果在，则对应关系就是：
$$
J_{n, k} = (J_{n - n / k, k} + k\times[n/k]) \% n \
所以先减去n \% k，小于0则加上n即可。
$$
如果不在这个范围内，注意此时原序列编号0对应n \% k，因为J_{n - n / k, k}已经减去了n % k，对应的序列是：
$$
原编号：0,1,2,\cdots k - 2, k\cdots \
子问题编号：n \%k, n\% k + 1 ,\cdots,
$$
所以也就是每经过k-1的长度就需要补偿1，所以对应else部分的代码。
时间复杂度的证明：
假设递归的次数是x，那么每一次问题的规模会变成n - [n / k]，如果这里做一下近似处理，则可以认为规模变成了n(1 - \frac{1}{n})，于是得到： $$ n(1 - \frac{1}{n})^ x = 1 \ x = -\frac{\ln n}{\ln(1 - \frac{1}{k})} $$ 考虑计算\lim _{k \rightarrow \infty} k \log \left(1-\frac{1}{k}\right)，有： $$ \begin{aligned} \lim _{k \rightarrow \infty} k \log \left(1-\frac{1}{k}\right) &=\lim _{k \rightarrow \infty} \frac{\log \left(1-\frac{1}{k}\right)}{1 / k} \ &=\lim _{k \rightarrow \infty} \frac{\frac{\frac{\mathrm{d}}{\mathrm{d} k} \log \left(1-\frac{1}{k}\right)}{\frac{\mathrm{d}}{\mathrm{d} k}\left(\frac{1}{k}\right)}}{ } \ &=\lim _{k \rightarrow \infty} \frac{\frac{1}{k^{2}\left(1-\frac{1}{k}\right)}}{-\lim _{k \rightarrow \infty}-\frac{k}{k-1}} \ &=-\lim _{k \rightarrow \infty} \frac{1}{1-\frac{1}{k}} \ &=-1 \end{aligned} $$ 于是： $$ x = -\frac{\ln n}{\ln(1 - \frac{1}{k})} = -\frac{k\ln n}{k\ln(1 - \frac{1}{k})} = k\log n $$ 所以时间复杂度是O(k \log n)。
典型题目：
- HDU 3089 Josephus again
- CF 101955 problem K
- SJTU OJ 4089 约瑟夫环（当时用数组模拟的）
- LeetCode 面试题 62 圆圈中最后剩下的数字（采用模拟的方法会超时）
- POJ 2886 （线段树 + 单点修改 + 约瑟夫环）