题目连接：http://poj.org/problem?id=2886
这道题是模拟约瑟夫环，其具体实现和poj2826差不多的。
我的代码如下：
#include<cstdio> #include<cstdlib> #include<cmath> #include<memory.h> int seg_tree[500010<<2]; void build_tree(int l,int r,int id); void push_tree_up(int id); void update_tree(int value,int l,int r,int id); int f[500010]; void get_f(); int num[500010],h; char str[500010][10]; int cur_n,cur_i,next_i,ans,ans1; int main() { int n,k,i,j,cur,temp; //freopen("d:\\2.txt","r",stdin); //freopen("d:\\3.txt","w",stdout); memset(f,0,sizeof(f)); get_f(); while(scanf("%d%d%*c",&n,&k)!=EOF) { for(i=1;i<=n;i++) scanf("%s%d",str[i],num+i); cur_n=n; cur_i=n; next_i=k; build_tree(1,n,1); ans=0; ans1=1; h=1; for(i=1;i<=n;i++) { // printf("cur_i=%d next_i=%d",cur_i,next_i); if(next_i>=0) cur_i--; cur=(cur_i+next_i%cur_n+cur_n)%cur_n; // printf(" cur=%d\n",cur); update_tree(cur+1,1,n,1); cur_i=cur; h++; } printf("%s %d\n",str[ans1],ans); } } void build_tree(int l,int r,int id) { if(l==r) { seg_tree[id]=1; return ; } int mid=(l+r)>>1; build_tree(l,mid,id<<1); build_tree(mid+1,r,id<<1|1); push_tree_up(id); } void push_tree_up(int id) { seg_tree[id]=seg_tree[id<<1]+seg_tree[id<<1|1]; } void update_tree(int value,int l,int r,int id) { if(l==r) { seg_tree[id]--; // printf("tree[id]=%d",seg_tree[id]); // printf("l=%d\n",l); next_i=num[l]; cur_n--; if(ans<f[h]) { ans=f[h]; ans1=l; } return ; } int mid=l+r>>1; if(value<=seg_tree[id<<1]) { update_tree(value,l,mid,id<<1); } else { update_tree(value-seg_tree[id<<1],mid+1,r,id<<1|1); } push_tree_up(id); } void get_f() { int i,j; for(i=1;i<=500000;i++) for(j=1;i*j<=500000;j++) { f[i*j]++; } }