WIKIOI 1282 约瑟夫问题

题目描述 Description

有编号从1到N的N个小朋友在玩一种出圈的游戏。开始时N个小朋友围成一圈，编号为I+1的小朋友站在编号为I小朋友左边。编号为1的小朋友站在编号为N的小朋友左边。首先编号为1的小朋友开始报数，接着站在左边的小朋友顺序报数，直到数到某个数字M时就出圈。直到只剩下1个小朋友，则游戏完毕。

现在给定N,M，求N个小朋友的出圈顺序。

输入描述 Input Description

唯一的一行包含两个整数N,M。（1<=N,M<=30000）

输出描述 Output Description

唯一的一行包含N个整数，每两个整数中间用空格隔开，第I个整数表示第I个出圈的小朋友的编号。

样例输入 Sample Input

5 3

样例输出 Sample Output

3 1 5 2 4

模拟的话复杂度O(MN) 会超时

求最后出圈人 有O(N)的算法

对于求顺序的 有O(NlogN)的算法

用线段树实现

因为线段树是维护区间信息的数据结构

主要思想就是 根节点0 1 表示是否在圈内 维护一个sumv的线段树

当前出圈人是第pos人 下一次是第pos+n-1人 因为刚才pos出去了 所以要-1  为了防止它大于sumv[1] 所以要%sumv[1] 又为了防止它是第0个人 所以特判一下

注意是人不是编号  而线段树维护的就是在圈内的人的数量

所以可以递归找到是哪个根节点 然后输出它对应的编号

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int lim=30033;
int sumv[lim<<2];
int m,n,want,pos;
int num[lim<<2],rank;

void pushup(int o){sumv[o]=sumv[o<<1]+sumv[o<<1|1];}

void build(int o,int l,int r)
{
    if(l==r)
    {
        sumv[o]=1;
        rank++;
        num[o]=rank;
        return;
    }
    int m=(l+r)>>1;
    build(o<<1,l,m);
    build(o<<1|1,m+1,r);
    pushup(o);
}

void del(int o,int l,int r)
{
    if(l==r)
    {
        sumv[o]=0;
        cout<<num[o]<<' ';
        return;
    }
    int m=(l+r)>>1;
    if(want<=sumv[o<<1])del(o<<1,l,m);
    else
    {
        want-=sumv[o<<1];
        del(o<<1|1,m+1,r);
    }
    pushup(o);
}

int main()
{
    scanf("%d%d",&m,&n);
    n%=m;
    if(n==0)n=m;
    build(1,1,m);
    pos=1;
    while(sumv[1])
    {
        pos=(pos+n-1)%sumv[1];
        if(pos==0)pos=sumv[1];
        want=pos;
        del(1,1,m);
    }
    return 0;
}