玩游戏

题目

n 个同学围成一圈，编号 1 到 n，从1号开始报数。第 i 轮报数到 a_i 的人被淘汰，下一轮从被淘汰者的下一个人开始，输出淘汰顺序。

输入：第1行为 n，第2行为 n 个整数 a₁, a₂, …, a_n。
输出：n 个整数，表示每轮被淘汰的编号。
数据范围：n ≤ 1000，a_i ≤ 10⁸。

样例1：

10
3 3 3 3 3 3 3 3 3 3

3 6 9 2 7 1 8 5 10 4

样例2：

10
3 4 5 6 9 20 1 2 4 5

3 7 2 10 5 4 6 9 8 1

提示：对于50%的数据，n ≤ 100，a_i ≤ 10000。对于100%的数据，n ≤ 1000，a_i ≤ 10⁸。

思路

（借助AI）用 vector 模拟这个不断缩小的圈：初始存入编号 1 到 n，用变量 cur 记录每轮报数的起始位置（0-indexed）。

每轮淘汰位置为 pos = (cur + a[c] - 1) % v.size()——从 cur 数 a[c] 个人，减1是因为 cur 本身算第1个，取模处理绕圈。输出 v[pos] 后用 v.erase(v.begin() + pos) 删除该元素，圈自动缩小。更新 cur = pos % v.size()，即下一轮从被淘汰者的后一位开始，最后一轮特判 v.size() > 0 防止除零。

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

int main(){
    int n;
    cin>>n;

    vector<int> a(n);
    for(int c=0;c<n;c++) cin>>a[c];

    vector<int> v(n);
    for(int c=0;c<n;c++) v[c]=c+1;

    int cur=0;

    for(int c=0;c<n;c++){
        int pos=(cur+a[c]-1)%v.size();
        cout<<v[pos]<<" ";
        v.erase(v.begin()+pos);
        if(v.size()>0) cur=pos%v.size();
    }

    return 0;
}

复杂度分析

• 时间复杂度：O(n²)，每轮 erase 最坏移动 n 个元素，共 n 轮。
• 空间复杂度：O(n)，vector 存储 n 个编号。

← 返回菜鸟的coding