P76059 循环报数出队 — 题解

专题： STL
适用题目： 新生 OJ 本地题包中的 P76059，不要直接用于外站同名题。

解题思路

用 queue<int> 存 1 到 n，反复将前 k-1 个人移到队尾，再移除第 k 人。

复杂度

时间 $O(nk)$，空间 $O(n)$。

易错点

每移除一人，从下一位继续报数；k=1 直接依次出队。

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

template<typename T>
void putvec(const vector<T>& a) {
    for (int i = 0; i < (int)a.size(); i++) {
        if (i) cout << ' ';
        cout << a[i];
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin>>n>>k;
    queue<int>q;
    vector<int>ans;
    for(int i=1;i<=n;i++)q.push(i);
    while(!q.empty()){
        for(int j=1;j<k;j++){
            q.push(q.front());
            q.pop();
        }
        ans.push_back(q.front());
        q.pop();
    }
    putvec(ans);
    return 0;
}

为什么只提供 C++： 本题专题要求使用 STL 容器或算法，C 语言没有 STL；C 可以用手写数据结构解决，但不属于本专题的教学目标。

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。