wikio p1282 约瑟夫问题

发布时间:2016-12-10 9:11:09 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"wikio p1282 约瑟夫问题",主要涉及到wikio p1282 约瑟夫问题方面的内容,对于wikio p1282 约瑟夫问题感兴趣的同学可以参考一下。

首先这道题目的数据规模还是很大的,而且数据也比较强大的。 所以这题需要用到线段树。 首先建立线段树,建立孩子信息,以及该子树未出局的小朋友数量。 我们建立好之后,可以add一下,计算还有多少孩子没有出局(当然如果通过循环,N-i+1就是剩余的孩子数量) 把M%=N-i+1 这样可以做到优化,如果空循环的话不仅没有用而且可能会导致超时。 这个时候我们应该有一个上一个报到的孩子编号,然后然后判断一下下一个报M的孩子是在1~上一个孩子的编号i之间,还是在i+1~N之间 当搜索到[s,t]这个区间的时候,判断一下是在左孩子的区间,还是在右孩子的区间,当然如果在右区间当中,应该把报到的编号加上左区间的孩子剩余数量。 题目还是很简单的。 当然数据强大,要不然谁会这么无聊用线段树。   #include<stdio.h> #include<iostream> #include<memory.h> using namespace std; const int MAX_N = 30001; const int root = 1; int N,M,P; struct node { int left,right; int data; }T[MAX_N*10]; int ans[MAX_N]; int BuildTree(int t,int l,int r) { if (l>r) return 0; if (l==r) { T[t].left=l; T[t].right=r; T[t].data=1; return T[t].data; } int mid=(l+r)/2; T[t].left=l; T[t].right=r; return T[t].data=BuildTree(t*2,l,mid)+BuildTree(t*2+1,mid+1,r); } int init() { scanf("%d %d",&N,&M); BuildTree(root,1,N); } int add(int t,int l,int r) { if (l>r) return 0; if (l==T[t].left&&r==T[t].right) return T[t].data; int mid=(T[t].left+T[t].right)/2; if (r<=mid) return add(t*2,l,r); if (l>mid) return add(t*2+1,l,r); return add(t*2,l,mid)+add(t*2+1,mid+1,r); } int next(int t) { if (t==N) return 1; else return t+1; } int Tree_Delete(int t,int v) { if (T[t].left==T[t].right) return T[t].data=0; int mid=(T[t].left+T[t].right)/2; T[t].data--; if (v<=mid) return Tree_Delete(t*2,v); if (v>mid) return Tree_Delete(t*2+1,v); } int search(int t,int l,int r,int p) { if (T[t].left==T[t].right) return T[t].left; int mid=(T[t].left+T[t].right)/2; if (r<=mid) return search(t*2,l,r,p); if (l>mid) return search(t*2+1,l,r,p); if (add(t*2,l,mid)>=p) return search(t*2,l,mid,p); else return search(t*2+1,mid+1,r,p-add(t*2,l,mid)); } int work() { int i; for (i=1;i<=N;i++) { P=(M-1)%(N-i+1)+1; if (add(root,ans[i-1]+1,N)>=P) ans[i]=search(root,ans[i-1]+1,N,P); else ans[i]=search(root,1,ans[i-1],P-add(root,ans[i-1]+1,N)); Tree_Delete(root,ans[i]); } } int put() { int i; for (i=1;i<=N;i++) printf("%d ",ans[i]); } int main() { init(); work(); put(); return 0; }

上一篇:常见排序算法的实现
下一篇:QT 5.0.2 VS2010开发环境搭建

相关文章

相关评论