AcWing 3559. 围圈报数-JZTXT

考点：约瑟夫环问题，环形链表，队列

#include <bits/stdc++.h>
using namespace std;

const int N = 55;
int ne[N];//链表指针数组

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        for (int i = 1; i < n; i++) ne[i] = i + 1;//环形链表初始化，1->2, 2->3,...
        ne[n] = 1;//最后一个点指向1
        
        int p = n;//p初始时指向1的前一个数。
        while(n--)
        {
            p = ne[ne[p]];//走两步（数到三时删除）
            cout << ne[p] << ' ';
            ne[p] = ne[ne[p]];//改变环形结构，相当于把报数到3的人踢出
        }
        cout << '\n';
    }
    return 0;
}

AcWing

3559