ural 1521. War Games 2 约瑟夫环 SBT实现

1521. War Games 2

Time Limit: 1.0 second
Memory Limit: 16 MB

Background

During the latest war games (this story is fully described in the problem "War games") the Minister of Defense of the Soviet Federation comrade Ivanov had a good chance to make sure personally, that an alertness of the Soviet Army under his command is just brilliant. But there was a thing, that continued to worry him. Being an outstanding commander, he realized, that only physical conditions of the soldiers were demonstrated. So the time came to organize one more war games and examine their mental capacity.

General Rascal was appointed to be responsible for the war games again. The general donated the allocated funds to the poor and went to bed free-hearted. In his dream, the tactics manual appeared to him and described a scheme, that allows to organize the war games absolutely free of charge.

Problem

In accordance with this scheme, the war games are divided into N phases; and Nsoldiers, successively numbered from 1 to N, are marching round a circle one after another, i.e. the first follows the second, the second follows the third, ..., the (N-1)-th follows the N-th, and the N-th follows the first. At each phase, a single soldier leaves the circle and goes to clean the WC, while the others continue to march. At some phase, the circle is left by a soldier, who is marching K positions before the one, who left the circle at the previous phase. A soldier, whose number is K, leaves the circle at the first phase.

Surely, Mr. Rascal cherished no hope about his soldiers' abilities to determine an order of leaving the circle. "These fools can not even paint the grass properly", - he sniffed scornfully and went to sergeant Filcher for an assistance.

Input

The only line contains the integer numbers N (1 ≤ N ≤ 100000) and K (1 ≤ K ≤ N).

Output

You should output the numbers of soldiers as they leave the circle. The numbers should be separated by single spaces.

Sample

input	output
5 3	3 1 5 2 4

题目抽象描述：
N个人围成一圈顺序编号，从1号开始按1、2、3......顺序报数，报p者退出圈外，其余的人再从1、2、3开始报数，报p的人再退出圈外，以此类推。
请按退出顺序输出每个退出人的原序号。

输入：
包括一个整数N(1<=N<=100000)及一个整数p。

输出：
测试数据可能有多组，对于每一组数据，
按退出顺序输出每个退出人的原序号。

样例输入：

5 3

样例输出：
3 1 5 2 4

分析：
先把所有人插入到SBT中，然后出去的时候，把他从SBT中删除，而找到要删除的元素为pos = (pre+k-1)%n+1，n每出去一个人减一，而pre从0开始，若已经有人出队，则置为上一个人出队的位置减一，然后就是找到第pos小即可

代码如下：

View Code

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 
  5 using namespace std;
  6 
  7 const int X = 100005;
  8 
  9 int root,tol,n,m;
 10 
 11 struct node{
 12     int val,l,r,s;
 13     void init(int _val){
 14         l = r = 0;
 15         s = 1;
 16         val = _val;
 17     }
 18 }sbt[X];
 19 
 20 void left_rotate(int &t){
 21     int k = sbt[t].r;
 22     sbt[t].r = sbt[k].l;
 23     sbt[k].l = t;
 24     sbt[k].s = sbt[t].s;
 25     sbt[t].s = sbt[sbt[t].l].s+sbt[sbt[t].r].s+1;
 26     t = k;
 27 }
 28 
 29 void right_rotate(int &t){
 30     int k = sbt[t].l;
 31     sbt[t].l = sbt[k].r;
 32     sbt[k].r = t;
 33     sbt[k].s = sbt[t].s;
 34     sbt[t].s = sbt[sbt[t].l].s+sbt[sbt[t].r].s+1;
 35     t = k;
 36 }
 37 
 38 void maintain(int &t,bool ok){
 39     if(!ok){
 40         if(sbt[sbt[sbt[t].l].l].s>sbt[sbt[t].r].s)
 41             right_rotate(t);
 42         else if(sbt[sbt[sbt[t].l].r].s>sbt[sbt[t].r].s){
 43             left_rotate(sbt[t].l);
 44             right_rotate(t);
 45         }
 46         else return;
 47     }
 48     else{
 49         if(sbt[sbt[sbt[t].r].r].s>sbt[sbt[t].l].s)
 50             left_rotate(t);
 51         else if(sbt[sbt[sbt[t].r].l].s>sbt[sbt[t].l].s){
 52             right_rotate(sbt[t].r);
 53             left_rotate(t);
 54         }
 55         else return;
 56     }
 57     maintain(sbt[t].l,0);
 58     maintain(sbt[t].r,1);
 59     maintain(t,0);
 60     maintain(t,1);
 61 }
 62 
 63 void insert(int &t,int val){
 64     if(!t){
 65         t = ++tol;
 66         sbt[t].init(val);
 67         return;
 68     }
 69     sbt[t].s++;
 70     if(val<sbt[t].val)
 71         insert(sbt[t].l,val);
 72     else
 73         insert(sbt[t].r,val);
 74     maintain(t,val>=sbt[t].val);
 75 }
 76 
 77 int del(int &t,int val){
 78     if(!t)  return 0;
 79     sbt[t].s--;
 80     if(val==sbt[t].val||(val<sbt[t].val&&!sbt[t].l)||(val>sbt[t].val&&!sbt[t].r)){
 81         if(sbt[t].l&&sbt[t].r){
 82             int pos = del(sbt[t].l,val+1);
 83             sbt[t].val = sbt[pos].val;
 84             return pos;
 85         }
 86         else{
 87             int pos = t;
 88             t = sbt[t].l+sbt[t].r;
 89             return pos;
 90         }
 91     }
 92     else
 93         return del(val<sbt[t].val?sbt[t].l:sbt[t].r,val);
 94 }
 95 
 96 int find_k_min(int &t,int k){   //找到第k小
 97     if(k<=sbt[sbt[t].l].s)
 98         return find_k_min(sbt[t].l,k);
 99     else if(k>sbt[sbt[t].l].s+1)
100         return find_k_min(sbt[t].r,k-sbt[sbt[t].l].s-1);
101     else
102         return sbt[t].val;
103 }
104 
105 int main()
106 {
107     freopen("sum.in","r",stdin);
108     freopen("sum.out","w",stdout);
109     while(cin>>n>>m){
110         int pos = 0,temp,val;
111         root = tol = 0;
112         for(int i=1;i<=n;i++)
113             insert(root,i);
114         while(n){
115             temp = (pos+m-1)%n+1;
116             pos = temp-1;
117             val = find_k_min(root,temp);
118             del(root,val);
119             printf("%d",val);
120             if(n>1)
121                 putchar(' ');
122             n--;
123         }
124         puts("");
125     }
126     return 0;
127 }