题目描述 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
数据范围及提示 Data Size & Hint
思路:
坑爹到炸的线段树;;;
其实用模拟就能过,但是我依然写的线段树
刚开始想复杂了,将近150行代码还全部wa
ac的思路很简单
就是模拟当先场上还有几个人
线段树上每个节点的值为1
表示这个人还在场上
然后维护还在场上的人的个数
然后每次输出这次out的是场上第几人
删除的时候只需把他的值改为0
来,上代码:
#include <cstdio> using namespace std; struct node {
int l,r,dis,mid; void mid_()
{
mid=(l+r)>>;
}
};
struct node tree[*+]; int n,m; inline void tree_up(int now)
{
tree[now].dis=tree[now<<].dis+tree[now<<|].dis;
} void tree_build(int now,int l,int r)
{
tree[now].l=l,tree[now].r=r;
if(l==r)
{
tree[now].dis=;
return ;
}
tree[now].mid_();
tree_build(now<<,l,tree[now].mid);
tree_build(now<<|,tree[now].mid+,r);
tree_up(now);
return ;
} int tree_out(int now,int ci)
{
if(tree[now].l==tree[now].r)
{
tree[now].dis=;
return tree[now].l;
}
if(tree[now<<].dis<ci) ci=tree_out(now<<|,ci-tree[now<<].dis);
else ci=tree_out(now<<,ci);
tree_up(now);
return ci;
} int main()
{
scanf("%d%d",&n,&m);
tree_build(,,n);
int now=;
do
{
now=(now-+m)%n;
printf("%d ",tree_out(,now+));
} while(--n);
return ;
}