一本通-1334：【例2-3】围圈报数（数组模拟循环链表或者队列模拟）

【题目描述】 有ｎ个人依次围成一圈，从第１个人开始报数，数到第ｍ个人出列，然后从出列的下一个人开始报数，数到第ｍ个人又出列，…，如此反复到所有的人全部出列为止。设ｎ个人的编号分别为1，2，…，n，打印出列的顺序。

【输入】 n和m。

【输出】 出列的顺序。

【输入样例】 4 17

【输出样例】 1 3 4 2

---

方法一：队列模拟

#include <bits/stdc++.h>

using namespace std;

void solve(int n, int m)
{
    queue<int> q;
    for (int i = 1; i <= n; ++i) q.push(i);

    while (!q.empty()) {
        int len = q.size();
        int mode = m % len == 0 ? len : m % len;
        for (int i = 0; i < mode - 1; ++i) {
            q.push(q.front()); q.pop();
        }
        cout << q.front() << ' ';
        q.pop();
    }
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n >> m;
    solve(n, m);

    return 0;
}

方法二：用数组模拟循环链表。是一种很好的思路，实现起来也带有一定的技巧，但是存在一个问题，比如这个m很大，如果用链表去模拟会很浪费时间，效率上不如用队列模拟。当然也存在解决办法，就是用一个变量去记录目前链表的长度，每次用m对长度取模，其实和用队列的方式基本一致。

技巧性再17行和20行的代码，用start去存储应该被删除的节点的前一个节点。

#include <bits/stdc++.h>

using namespace std;


vector<int> seq(105);
int n, m;


void solve()
{
    //建立链接
    for (int i = 1; i < n; ++i) seq[i] = i + 1;
    seq[n] = 1;

    //模拟出队
    int start = n;
    for (int cnt = 0; cnt < n; ++cnt) {
        for (int i = 0; i < m - 1; ++i) {
            start = seq[start];
        }
        cout << seq[start] << ' ';
        seq[start] = seq[seq[start]];
    }   
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    solve();

    return 0;
}