约瑟夫问题
sun_and_moon · · 算法·理论
::::info[约瑟夫问题]{open}
AC代码：
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671
#define maxn 1000005
using namespace std;
int a[maxn];
int f,t,s;
int ans;
int n,k;
int main()
{
cin>>n>>k;
while(f<n)
{
t++;//现在报数报到的位置
if(t>n)
t=1;
if(a[t]==0)
{
s++;//这人还在，报数！
if(s==k)//这人该出圈了
{
a[t]=1;
f++;//又出圈了一个
s=0;//重新报数
if(lx==0)
cout<<t<<' ';
else
ans=t;
}
}
}
if(lx==1)
cout<<ans;
return 0;
}方法二：链表——O(nk)
AC代码：
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671
#define maxn 1000005
using namespace std;
int a[maxn];//链表指针数组~
int f,t,s;
int ans;
int n,k;
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
a[i]=i+1;
a[n]=1;
while(f<n)
{
t=a[t];//下一个位置 ~
s++;//报数 ——
if(s==k-1)//场外贵宾一位！（出圈）
{
if(lx==1)
ans=a[t];
else
cout<<a[t]<<' ';
a[t]=a[a[t]];
s=0;
f++;
}
}
if(lx==1)
cout<<ans;
return 0;
}方法三：模拟——O(nk)
AC代码：
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671
#define maxn 1000005
using namespace std;
int a[maxn];//现在坐在i位置的人是谁呢？当然是a[i]咯~
int f,t,s;
int ans;
int n,k;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
a[i]=i;
for(s=1,f=n;f>=1;f--)//每轮循环都能有“场外贵宾一位！”（出圈大吉）
{
s=(s+k-2)%f+1;//下一位场外贵宾！
if(lx==0)
cout<<a[s]<<' ';
else
ans=a[s];
for(int j=s;j<f;j++)//后面的，都给我往左移一位！
a[j]=a[j+1];
}
if(lx==1)
cout<<ans;
return 0;
}方法四：分块——O(n\sqrt{n})
AC代码：
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671
#define maxn 1000005
using namespace std;
bool a[maxn];//现在编号为 i 人还好吗？a[i] 为 1 就还好
int b[maxn];//现在 i 组还有几个人？b[i]个人~
int c;//初始一组几个人？这个变量告诉你~
int f,t,s;
int ans;
int n,k;
int main()
{
cin>>n>>k;
k=(k-1)%n+1;
c=sqrt(n);
s=1;
for(int i=1;i<=n;i++)
{
a[i]=true;
b[i/c]++;
}
for(f=n;f>=1;f--)//每轮循环，贵宾一位！
{
s=(s+k-2)%f+1;
int x=s,l=0;
while(b[l]<x)
x-=b[l++];
t=l*c-1;
while(x)
x-=a[++t];
if(lx==0)
cout<<t<<' ';
else
ans=t;
a[t]=false;//贵宾走了，但他的位置还在……
b[t/c]--;//小组人数--
}
if(lx==1)
cout<<ans;
return 0;
}方法五：线段树——O(n \log n)
AC代码：
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671
#define maxn 1000005
using namespace std;
int tree[maxn*4]; //线段树要吃四倍空间？！太吓人啦！
int f,s=1,t;
int ans;
int n,k;
void build(int i,int l,int r)//建树！（要致富，先撸树）
{
if(l==r)
{
tree[i]=1;
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
tree[i]=tree[i*2]+tree[i*2+1];
}
void update(int i,int l,int r,int u,int v)//修改其中一点的数值！（小心树木倒塌）
{
if(l==r)
{
tree[i]=v;
return;
}
int mid=(l+r)/2;
if(u<=mid)
update(i*2,l,mid,u,v);
else
update(i*2+1,mid+1,r,u,v);
tree[i]=tree[i*2]+tree[i*2+1];
return;
}
int query(int i,int l,int r,int k)//查询其中一点的数值！（树木不好查）
{
if(l==r)
return l;
int mid=(l+r)/2;
if(k<=tree[i*2])
return query(i*2,l,mid,k);
else
return query(i*2+1,mid+1,r,k-tree[i*2]);
}
int main()
{
cin>>n>>k;
build(1,1,n);
for(f=n;f>=1;f--)//这次邀请贵宾，咱要用线段树！
{
s=(s+k-2)%f+1;
t=query(1,1,n,s);
if(lx==0)
cout<<t<<' ';
else
ans=t;
update(1,1,n,t,0);
}
if(lx==1)
cout<<ans;
return 0;
}方法六：树状数组——O(n \log n \log n)
AC代码：
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671
#define maxn 1000005
using namespace std;
int tree[maxn]; //树状数组比线段树要好多啦 ~不多吃空间 ~
int f,s=1,t;
int ans;
int n,k;
void update(int i,int r,int v)//增加其中一点的数值！（小心树木倒塌）
{
for(int x=i;x<=r;x+=x&-x)
tree[x]+=v;
return;
}
bool check(int mid)//二分判断条件
{
int sum=0;
for(int x=mid;x>0;x-=x&-x)
sum+=tree[x];
return sum>=s;
}
int ef(int l,int r)//咱要节省时间……O(n)~O(log n)
{
while(l<r)
{
int mid=(l+r)/2;
if(check(mid))
r=mid;
else
l=mid+1;
}
return r;
}
void build(int i,int r)//建树！（要致富，先撸树）
{
for(int j=i;j<=r;j++)
update(j,r,1);
}
int main()
{
cin>>n>>k;
build(1,n);
for(f=n;f>=1;f--)//这次邀请贵宾，咱要用……树状数组！
{
s=(s+k-2)%f+1;
ans=ef(1,n);
if(lx==0)
cout<<ans<<' ';
update(ans,n,-1);
}
if(lx==1)
cout<<ans;
return 0;
}方法七：块状链表——O(n\sqrt{n})
AC代码：
#include<bits/stdc++.h>
#define lx 0 //0为P1996，1为P8671
#define maxn 1000005
using namespace std;
bool a[maxn];//现在编号为 i 人还好吗？a[i] 为 1 就还好
struct lb
{
int next;
vector<int>v;
}b[maxn];//现在 i 组还有几个人？b[i].v.size()个人~
int c;//初始一组几个人？这个变量告诉你~
int f,t,s;
int ans;
int n,k;
int main()
{
cin>>n>>k;
k=(k-1)%n+1;
c=sqrt(n);
s=1;
for(int i=1;i<=n;i++)
{
a[i]=true;
b[i/c].v.push_back(i);
}
for(int i=0;i<n;i++)
b[i].next=i+1;
for(f=n;f>=1;f--)//每轮循环，贵宾一位！
{
s=(s+k-2)%f+1;
int x=s,l=0;
while(b[l].v.size()<x)
{
x-=b[l].v.size();
l=b[l].next;
}
t=l*c-1;
if(lx==0)
cout<<b[l].v[x-1]<<' ';
else
ans=b[l].v[x-1];
a[t]=false;//贵宾走了，但他的位置还在……
b[l].v.erase(b[l].v.begin()+x-1);//不好！他在vector里的位置没了！！！
}
if(lx==1)
cout<<ans;
return 0;
}方法八：递归——O(n)
注：此代码仅限P8671
AC代码：
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int n,k;
int f(int n)
{
if(n==1)
return 1;
return (f(n-1)+k-1)%n+1;
}
int main()
{
cin>>n>>k;
cout<<f(n);
return 0;
}方法九：递推——O(n)
注：此代码仅限P8671
AC代码：
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int ans=1;
int n,k;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
ans=(ans+k-1)%i+1;
cout<<ans;
return 0;
}方法十：递归优化——O(k)
注：此代码仅限P8671
AC代码：
//方法十
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
int k;
int f(int n)
{
if(n==1)
return 1;
return (f(n-1)+k-1)%n+1;
}
int fk(int n)
{
if(n<k)
return f(n);
int l=fk(n-n/k),y=n%k;
if(l<=y)
return l+n/k*k;
l-=y;
return (l-1)/(k-1)+l;
}
int n;
int main()
{
cin>>n>>k;
cout<<fk(n);
return 0;
}