围圈报数

题目 围圈报数

思路分析

构建一个循环链表。

void init() {

for (int i = 1; i < n; i ++ )

ne[ ++ idx] = i + 1;

ne[ ++ idx] = 1;

}

具体操作过程如下图所示：

构建完成循环链表后，每次报数为 3的人退出圈外，即进行链表的删除操作。那么我们如何去找报数为 3的那个人呢？ 我们设 start为我们的开始结点。则报数为 3的那个人一定是 ne[ne[start]]，并且更新 start的位置。

具体操作过程如下图所示：

代码实现

#include<bits/stdc++.h>

using namespace std;

const int N=55;

int ne[N],idx;

int T,n;

void init()

{

    memset(ne,0,(n+1)*4);

    idx=0;

    for(int i=1;i<n;i++)

        ne[++idx]=i+1;

    ne[++idx]=1;

}

void del(int x){

    ne[x]=ne[ne[x]];

}

int main()

{

    cin>>T;

    while(T--){

        cin>>n;

        init();

        int start=1;

        for(int i=1;i<=n;i++){

            int now=ne[ne[start]];

            cout<<now<<" ";

            del(ne[start]);

            start=ne[ne[start]];

        }

        cout<<endl;

    }

    return 0;

}

#include<bits/stdc++.h>

using namespace std;

int T,n;

int main()

{

    cin>>T;

    while(T--){

        cin>>n;

        list<int> nums;

        for(int i=1;i<=n;i++){

            nums.push_back(i);

        }

        auto it=nums.begin();

        int k=3-1;

        while(nums.size()){

            while(k--){

                it++;

                if(it==nums.end())

                    it=nums.begin();

            }

            cout<<*it<<" ";

            it=nums.erase(it);

            if(it==nums.end())

                it=nums.begin();

            k=3-1;

        }

        cout<<endl;

    }

    return 0;

}

同类题型

视频讲解

⬅️ 区块反转 🏠 00-刷题理模型 ➡️ 圆圈中最后剩下的数字