题解

1. 数组模拟链表

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

int n,m;
struct f{
	int x; //值
    int nxt; //下一个元素的指针
}a[105];

int main(){
    cin>>n>>m;
    
    for(int i=0;i<n;i++){ //先处理到 n-1，第 n 个特殊处理
    //a[0]实际上不参与报数
    	a[i].x=i;
        a[i].nxt=i+1; //此时数组有序，直接让 nxt 指向 i+1
    }
    //特殊处理
    a[n].x=n,a[n].nxt=1; //由于是一个环，所以 a[n] 指向第一个元素 
    
    int now=0; //初始化为 0，主要是方便后续操作
    for(int i=0;i<n;i++){ //让 n 个人出圈
        for(int j=1;j<m;j++){ //循环 m-1 次，让 now 一直向后移动，模拟报数
            now=a[now].nxt;
        }
        //循环结束，此时的 now 指向的是本轮第 m 个人的上一个人
        
        int pos_=a[now].nxt; //pos_代表需要出圈的那个人
        int pos_1=a[pos_].nxt; //pos_1代表需要出圈的下一个人
        
        a[now].nxt=pos_1; //忽略第 m 个元素，模拟出圈
        
        cout<<a[pos_].x<<' ';
    }
    
    return 0;
}

思路

数组模拟链表操作（可推广）：

要插入/删除的元素为 $k$，它的上一个元素/插入后下一个元素为 $k-1$，下一个元素/插入后下一个元素为 $k+1$

项目	内容
删除元素	把 $k-1$ 的指向下一个元素的指针设为 $k+1$
添加元素	先通过 $k-1$ 找到 $k+1$，把 $k$ 指向下一个元素的指针设为 $k+1$，把 $k-1$ 指向下一个元素的指针设为 $k$

2. stl实现

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

int n,m;
list<int> a; //不用 list<int> a(105)，因为这样的 105 个元素值都为 0

int main(){
    cin>>n>>m;
    
    for(int i=1;i<=n;i++){
        a.push_back(i); //手动初始化
    }
    
    auto it=a.begin();
    while(!a.empty()){
        for(int i=1;i<m;i++){ //注意：是 i<m ，因为当 i=m-1 时，it 已经落在第 m 个人身上了
            ++it;
            if(it==a.end()){
                it=a.begin();
        	} //变成环，如果加到 a.end() 去了就移回 a.begin()
        }
        cout<<*it<<' ';
        it=a.erase(it); //erase 是删除 it 指向的元素。因为删除后之前的迭代器会失效，所以需要用 erase 的返回值（有效迭代器）重新赋值给 it
        if(it==a.end()&&!a.empty()){
            it=a.begin();
        } //手动移回
    }
    
    return 0;
}

思路

• 为了实现一个环要手动处理迭代器，移回 a.begin()。
• erase 的用法：删除一个元素的同时返回新的有效迭代器的值（旧迭代器将不可用）。