首页 > 代码库 > wikioi 1282 约瑟夫问题 线段树
wikioi 1282 约瑟夫问题 线段树
和上一题一样,寻找第K个位置,只不过需要处理一下下一个位置在哪,画图看看就知道了。
#include <cstdio> #include <algorithm> #include <iostream> using namespace std; #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 const int maxn = 30000+5; int sum[maxn<<2],a[maxn]; void pushup(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void build(int l,int r,int rt) { if (l==r) {sum[rt]=1;return;} int m=(l+r)>>1; build(lson); build(rson); pushup(rt); } int update(int l,int r,int rt,int cnt) { int ret,m=(l+r)>>1; if(l==r) { sum[rt]=0; return l; } if(cnt<=sum[rt<<1]) ret=update(lson,cnt); else ret=update(rson,cnt-sum[rt<<1]); pushup(rt); return ret; } int main() { int x,st=1,n,m; scanf("%d%d",&n,&m); build(1,n,1); for(int i=1,last=n;i<=n;i++,last--) { x=(st+m-1)%last; if(x==0) x=last; st=x; a[i]=update(1,n,1,x); } for(int i=1;i<=n;i++) { if(i==1) printf("%d",a[i]); else printf(" %d",a[i]); } puts(""); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。