本文共 1490 字，大约阅读时间需要 4 分钟。

模拟的话复杂度O(MN) 会超时

求最后出圈人 有O(N)的算法

对于求顺序的 有O(NlogN)的算法

用线段树实现

因为线段树是维护区间信息的数据结构

主要思想就是 根节点0 1 表示是否在圈内 维护一个sumv的线段树

当前出圈人是第pos人 下一次是第pos+n-1人 因为刚才pos出去了 所以要-1  为了防止它大于sumv[1] 所以要%sumv[1] 又为了防止它是第0个人 所以特判一下

注意是人不是编号  而线段树维护的就是在圈内的人的数量

所以可以递归找到是哪个根节点 然后输出它对应的编号

#include
   
    #include
    
     #include
     
      using namespace std;const int lim=30033;int sumv[lim<<2];int m,n,want,pos;int num[lim<<2],rank;void pushup(int o){sumv[o]=sumv[o<<1]+sumv[o<<1|1];}void build(int o,int l,int r){    if(l==r)    {        sumv[o]=1;        rank++;        num[o]=rank;        return;    }    int m=(l+r)>>1;    build(o<<1,l,m);    build(o<<1|1,m+1,r);    pushup(o);}void del(int o,int l,int r){    if(l==r)    {        sumv[o]=0;        cout<
      
       <<' ';        return;    }    int m=(l+r)>>1;    if(want<=sumv[o<<1])del(o<<1,l,m);    else    {        want-=sumv[o<<1];        del(o<<1|1,m+1,r);    }    pushup(o);}int main(){    scanf("%d%d",&m,&n);    n%=m;    if(n==0)n=m;    build(1,1,m);    pos=1;    while(sumv[1])    {        pos=(pos+n-1)%sumv[1];        if(pos==0)pos=sumv[1];        want=pos;        del(1,1,m);    }    return 0;}
      
     
    
   

转载地址：https://blog.csdn.net/li412302070/article/details/13984733 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！