首页 > 代码库 > 约瑟夫环小结(线段树)
约瑟夫环小结(线段树)
题目大意:
输入初始人数编号为1~n,以及初始密码m,输出出局序列.
解法一:用线段树可解.
Segtree节点存储左右区间和该区间下包含的人数.
void Build(int p,int left,int right)表示从编号为p,区间为[l,r]的节点开始向下建树.
int Update(int p,int id)表示从编号为p的节点开始查询在新队伍中编号为id的人出局,返回该人在最初队伍中的编号.
而temp=(temp+m-1)%seg[1].manum;语句用于求出下一个出局的人在新队伍中的编号id,即传入Update()函数参数中的id.
Update()函数在递归过程中实现了给新队伍人员从1~n重新编号,如果id<=seg[p].manum,即p节点左子树最多能从1编号到seg[p].manum.
说明新队伍中编号为id的人在p节点的左子树中,则继续递归;反之,则在p节点的右子树中.
#include<cstdio> #define maxn 200010 struct Segtree { int l,r; int manum; }seg[4*maxn]; void Build(int p,int left,int right) { seg[p].l=left; seg[p].r=right; if(left==right){ seg[p].manum=1; return; } int mid=(left+right)/2; Build(2*p,left,mid); Build(2*p+1,mid+1,right); seg[p].manum=seg[2*p].manum+seg[2*p+1].manum; } int Update(int p,int id) { seg[p].manum--; if(seg[p].l==seg[p].r) return seg[p].l; if(id<=seg[2*p].manum) Update(2*p,id); else Update(2*p+1,id-seg[2*p].manum); } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF){ printf("%d",m); Build(1,1,n); Update(1,m); int temp=m; while(n>=2){ temp=(temp+m-1)%seg[1].manum; if(temp==0) temp=seg[1].manum; int id=Update(1,temp); printf(" %d",id),n--; } printf("\n"); } }
约瑟夫环小结(线段树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。