题解 P1996 【约瑟夫问题】

· · 题解

这道题直接模拟什么的话理论复杂度应该是O(n^{2})的吧，如果是比较大的数据范围就会挂掉,所以我们考虑O(nlogn)的算法。 最简单的当然就是树状数组啦。。

我们将问题转换一下，假设当前已经删除的人是第k大的，那么接下来要删除的人就是第（k+m-1）大的，这里暂时不考虑环。

那么我们就要维护一个数据结构，每次满足单点修改，全局查kth....

那就是权值树状数组啦。

也就是说下标就是人的编号，1和0代表人在不在

对于环形来说，我们每次对当前剩余人数取模即可。

还有最后的找kth的操作，我的另一篇博客里有具体的解释，有兴趣可以看看，网上也有类似的。

上代码：

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn=3e4+10;
int n,m,maxx;
int bit[maxn];

inline int lowbit(int x)
{
    return x&-x;
}
inline void add(int pos,int x)
{
    for(int i=pos;i<=maxx;i+=lowbit(i))bit[i]+=x;
}
inline int find_kth(int k)
{
    int ans=0,now=0;
    for(int i=15;i>=0;i--)
    {
        ans+=(1<<i);
        if(ans>maxx||bit[ans]+now>=k)ans-=(1<<i);
        else now+=bit[ans];
    }
    return ans+1;
}

int main()
{
    scanf("%d %d",&n,&m);
    maxx=n;     //这里因为n后面会改变，所以先记录一下n的值。 
    for(int i=1;i<=n;i++)bit[i]=lowbit(i);//这里完全等价于add(i,1),因为一开始都是1，所以bit[i]=i-(i-lowbit(i)+1)+1=lowbit(i) 
    int now=1;//从1开始 
    while(n)
    {
        now=(now-1+m-1)%n+1;//这里是小细节，本来的式子应该是(now+m-1)%n的，但是考虑如果只剩下2个元素，而我们当前要找的就是第二个元素呢？直接模就是0了，所以用一个+1 -1 的小操作更改取模运算的值域，这样就可以取到n的值了，而对别的无影响 
        int ans=find_kth(now);//找kth 
        add(ans,-1);//把这个人删除 
        printf("%d ",ans);
        n--;
    }
    return 0;
}