约瑟夫环问题（模板题，递推，树状数组，双端队列）

本文主要是介绍约瑟夫环问题（模板题，递推，树状数组，双端队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

其中皆有数学递推公式做法。 对于出局顺序还加了 双端队列，树状数组做法，时间复杂度更低。
最后还有编号从1开始，与从0开始的不同之处。

最后活的人（递推）

序列长度为10，target为3时

1 2 3 4 5 6 7 8 9 10

每死一个人，都会影响后面的报数，也就是确定了下一个要死的

第一个死的是3

第二个要死的是6变成的3

第三个死的，是9变成6又变成3

这就给我们提供了一个思路，可以通过记录每死一个人的状态，来归纳总结答案。

即，当活着的人数为$num$时，要死的是谁！

当长度为num-1,死的下标为f,由上表中3，6，9，可推得，该数字在长度为num时的下标F为

F=(f+target)%num

那最后留下的，只有它一个，下标自然就是1喽。不断向上递推不就得出，长度为num时，最后活着的人的下标了么。

请看下面例题：

LCR 187. 破冰游戏

class Solution {int f(int num,int target){if(num==1) return 0;int x=f(num-1,target);return (target+x)%num;}
public:int iceBreakingGame(int num, int target) {return f(num,target);}
};

class Solution {
public:int iceBreakingGame(int num, int target) {int f=0;for(int i=2;i!=num+1;i++)//长度为2到num{f=(target+f)%i;}return f;}
};

P8671 约瑟夫环 - 洛谷

出局顺序（递推，树状数组）

最后留下的编号为1，我们从上述表格也可得知，每次出局的编号为（target%num）,以10 3为例，出局时的编号为3

以9为例，它是第三个出局。

出局时编号返回3，利用上述递推公式，得出

第二局编号为 （3+3）%10=6

第一局编号为 （6+3）%10=9

这样我们就能得出第三局出局的是9

所以我们在上述代码中加一个循环，还有一个变量，控制每次递推次数，就可以得出每次出局的人了

同样的，我们先以编号从0开始为例，给出代码

递推代码（编号从0开始）

#include<bits/stdc++.h>
using namespace std;
//用递归实现约瑟夫环问题
int f(int N,int M,int i)
{if(i==1)//到达该数字出局时{return (M-1+N)%N;//因为从0开始，那么下标应该这样表示，且保证结果在0，N-1范围}return (f(N-1,M,i-1)+M)%N;
}int main()
{int num,target;cin>>num>>target;   for(int i=1;i<=num;i++)//第i个出局的递推i次cout<<f(num,target,i)<<" ";return 0;
} 

时间复杂度为O（$n^2$）.

L-koala的程序（双端队列）

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,k,pos=0;cin>>n>>k;deque<int> q;for(int i=1;i<=n;i++)q.push_back(i);while(q.size()>1){pos+=k-1;//因为队列从0开始while(pos+1>q.size()) pos-=q.size();cout<<q[pos]<<' ';q.erase(q.begin()+pos);}
}

树状数组

树状数组是 O（$NlongN$）时间复杂度。

用树状数组来存放初始位置每个人的状态。也就是N个人,每个人初始为1。

当一个人死了，标记该位置-1。

通过加k对当期序列长度取模，得到下一个该死的人在新序列中的编号p，结合二分 找到在 树状数组前缀和为p的位置，这就是原序列中该死的人，标记为-1.

先看代码，后面还有解释…

代码

#include <bits/stdc++.h>
using namespace std;
const int N=3e5+7;
#define lowbit(x) ((x)&(-x))
int tree[N],n,m;
void update(int i,int x){while(i<=n) {tree[i]+=x;i+=lowbit(i);}
}
int query(int x)
{int ans=0;while(x>0){ans+=tree[x];x-=lowbit(x);}return ans;
}
int main() {cin>>n>>m;int p=1;//初始化保证后面操作，一会儿会说for(int i=1;i<=n;++i) update(i,1);  //或这tree[i]=lower(i);  int t=n;while(t>1){p=(p+m-1-1)%t+1;//每次都有一个数-1被删，只需找到p-=1就好了int l=1,r=n;while(l<r){int mid=l+r>>1;if(query(mid)>=p) r=mid;else l=mid+1;}cout<<l<<' ';update(l,-1);t--;}return 0;
}

易错疑难点

为什么t=n

update操作也是需要n的，直接用$n--$，会影响结果正确性
要对不断递减的t取模

为什么p初始化1，循环里p=(p+m-1-1)%t+1这样更新值

1. (n-1)%m+1 这种-1+1取模，保证结果在【1，m】区间，符合编号

2. 我们是通过前缀和来找到要删除的数，可是在删除上一个数时，会使前缀和-1。所以我们原本要找sum=p，变成了sum=p-1，该位置是要找的。 可对于第一次进循环，没有数删除时，不需-1，因而初始化为1.

3. 也有代码初始就将$m--$ ,这样就不需要$p--$ 啦

编号从1开始

n%m

所得结果区间[0,m-1],恰巧符合下标从0开始

(n-1)%m+1

区间**[1,m]**,这样取模解决的这个问题。

所以上述代码中，将取模处和返回值修改一下就得出答案。

P8671 约瑟夫环 - 洛谷（最后活的人）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int f(int num,int target)
{if(num==1) return 1;//只剩一个数编号为1int x=f(num-1,target);return (target+x-1)%num+1;//上面说的，-1 +1 取模
}
signed main()
{IOSint n,k;cin>>n>>k;cout<<f(n,k);
}

出局顺序

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int f(int num,int target,int i){if(i==1) return (target-1)%num+1;int x=f(num-1,target,i-1);return (target+x-1)%num+1;}
signed main()
{IOSint num,target;cin>>num>>target;for(int i=1;i<=num;i++)cout<<f(num,target,i)<<" ";
}

这篇关于约瑟夫环问题（模板题，递推，树状数组，双端队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！