P4850 新的序列（基础）

解题思路

第一步，理解题意。 有一摞纸牌，从上往下编号是 1、2、3、……、n。我们一张一张地抽：抽到的第 1 张牌放到牌组最下面，第 2 张也放到最下面，抽到第 3 张（也就是"3 的倍数"那一张）时，这张牌就不放回去了，直接离开牌组。这样一直抽，直到所有牌都离开。把离开的牌按先后顺序排成一排，就是题目要的"新的序列"。

第二步，发现规律。 这其实就是一个"约瑟夫问题"：n 个人围成一圈报数，从 1 报到 3，报到 3 的人出圈，下一个人再从 1 开始报。就像小朋友玩"击鼓传花"，鼓声传到第 3 个人，他就要出列，然后从下一个人继续传。

第三步，用数组模拟。 开一个数组 a，a[i]=0 表示第 i 张牌还在牌组里，a[i]=1 表示已经离开。再用三个变量：pos 表示当前报到哪张牌，cnt 表示已经数到第几个，out 表示已经离开了几张牌。

第四步，循环报数。 每次 pos 向后走一格，走到 n 之后要回到 1（用 pos = pos % n + 1 实现），这样就能模拟"一圈一圈地转"。如果这张牌还在，就让 cnt 加 1；当 cnt 数到 3 时，这张牌离开牌组，输出它，out 加 1，cnt 重新变成 0。一直重复，直到 out 等于 n，也就是所有牌都离开牌组。

第五步，验证边界情况。 当牌组里只剩最后一张牌时，它需要自己连续被报到第 3 次才会离开，程序会自动转圈处理。数组要开成 a[10005]，比 n 的最大值 10000 大一点，防止越界。举个例子：n=5 时，1 报 1、2 报 2、3 报 3，所以 3 先离开；然后 4 报 1、5 报 2、1 报 3，1 离开……最后离开顺序是 3 1 5 2 4，和样例完全一致。

参考代码

// 新的序列：约瑟夫问题，n张牌报数，报到第3张时离开牌组
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    int a[10005] = {0};  // a[i]=0 表示牌 i 还在，1 表示已离开
    int out = 0;         // 已离开的牌数
    int pos = 0;         // 当前报数的位置
    int cnt = 0;         // 报数计数
    while (out < n) {
        pos = pos % n + 1;      // 循环向后移动
        if (a[pos] == 0) {      // 这张牌还没离开
            cnt++;
            if (cnt == 3) {     // 报到第3张，离开牌组
                a[pos] = 1;
                cout << pos;
                if (out < n - 1) cout << ' ';
                out++;
                cnt = 0;
            }
        }
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：每张牌离开前，最多可能要把一圈都转完，最坏情况下总共约 O(n²) 次操作。n 最大只有 10000，即使是 3 亿次循环，C++ 也能在 1 秒内完成，实际平均比这快得多，完全没问题。

空间复杂度：只用一个长度为 n+1 的数组，所以是 O(n)。