南郵 OJ 1190 約瑟夫問題

約瑟夫問題

時間限制(普通/Java) :  1000 MS/ 3000 MS          運作記憶體限制 : 65536 KByte

總送出 : 577            測試通過 : 50 

比賽描述

約瑟夫問題是一個非常經典的問題，它的問題描述是：有 n 個人圍成一圈，從第 1 個人開始，每次按順時針方向向後選擇第 m 個人，并将這個人出列。那麼你能高效的算出出列的順序嗎？

輸入

輸入資料有多組，每組輸入資料為一行，兩個正整數 n和m (1<=n，m<=30000)

輸出

每組輸出隻有一行，表示出列的順序。每兩個數字之間用一個空格分開。

樣例輸入

4 2

5 3

樣例輸出

2 4 3 1

3 1 5 2 4

提示

題目來源

李鴻斌（honghu）

#include<iostream>
#define N 30000
struct seg_tree{
	int l,r,m,num;
}st[N*4];
void build(long id,int l,int r){
	st[id].l = l;
	st[id].r = r;
	st[id].m = (l+r)>>1;
	st[id].num = r-l+1;
	if(l!=r){
		build(id<<1,l,st[id].m);
		build((id<<1)+1,st[id].m+1,r);
	}
}
int find_id(int k){//傳回剩下的數字中第k個數的id
	int id = 1;
	while(st[id].l!=st[id].r){
		if(k<=st[id<<1].num){
			id <<= 1;
		}else{
			k -= st[id<<1].num;
			id = (id<<1)+1;
		}
	}
	return st[id].l;
}
void del(int k){//删除剩餘數字鐘的第k個數
	int id=1;
	while(st[id].l!=st[id].r){
		--st[id].num;
		if(k<=st[id<<1].num){
			id <<= 1;
		}else{
			k -= st[id<<1].num;
			id = (id<<1)+1;
		}
	}
	--st[id].num;
	return;
}
int main(){
	int n,m,k;
	while(scanf("%d%d",&n,&m)!=EOF){
		memset(st,0,sizeof(st));
		build(1,1,n);
		k = 1;
		while(st[1].num){
			k = (k+m-1);
			k %= st[1].num;
			if(k==0){
				k = st[1].num;
			}
			printf("%d",find_id(k));
			if(st[1].num!=1){
				putchar(' ');
			}
			del(k);
		}
		putchar('\n');
	}
}