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;
}