首页 > 代码库 > AC日记——约瑟夫问题 codevs 1282
AC日记——约瑟夫问题 codevs 1282
1282 约瑟夫问题
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 大师 Master
题目描述 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)>>1; }};struct node tree[30000*4+1];int n,m;inline void tree_up(int now){ tree[now].dis=tree[now<<1].dis+tree[now<<1|1].dis;}void tree_build(int now,int l,int r){ tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].dis=1; return ; } tree[now].mid_(); tree_build(now<<1,l,tree[now].mid); tree_build(now<<1|1,tree[now].mid+1,r); tree_up(now); return ;}int tree_out(int now,int ci){ if(tree[now].l==tree[now].r) { tree[now].dis=0; return tree[now].l; } if(tree[now<<1].dis<ci) ci=tree_out(now<<1|1,ci-tree[now<<1].dis); else ci=tree_out(now<<1,ci); tree_up(now); return ci;}int main(){ scanf("%d%d",&n,&m); tree_build(1,1,n); int now=0; do { now=(now-1+m)%n; printf("%d ",tree_out(1,now+1)); } while(--n); return 0;}
AC日记——约瑟夫问题 codevs 1282
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。