CSES-2162 Josephus Problem I（链表）

题目传送门https://vjudge.net/problem/CSES-2162

解题思路

这是一道类似于约瑟夫问题的题目……

我们可以用链表解决！

都是链表的常规操作，没什么好说的。

代码

如果从 2 开始跳的话，可能要特判 n=1 的情况。

#include<bits/stdc++.h>
using namespace std;int n;int fr[200001],nxt[200001];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;if(n==1){cout<<1;return 0;}for(int i=1;i<n;i++)nxt[i]=i+1;nxt[n]=1;for(int i=2;i<=n;i++)fr[i]=i-1;fr[1]=n;int j=2;int cnt=1;while(cnt<=n){cout<<j<<" ";nxt[fr[j]]=nxt[j];fr[nxt[j]]=fr[j];cnt++;j=nxt[j];j=nxt[j];}return 0;
}