P4838 纸牌问题（入门）

解题思路

第一步，看懂操作规则。 桌面上有一叠牌，从上到下依次编号1到n，最上面的牌编号是1。只要这一叠牌还剩至少两张，就重复做两个动作：第一，把最上面（第一张）的牌扔掉；第二，再把此时最上面的那一张牌放到整叠牌的最下面。一直做到只剩一张牌为止。题目要求我们把每次扔掉的牌、以及最后剩下的那张牌，按顺序全部输出。

第二步，用队列模拟这叠牌。 队列的队头就是牌堆的顶部，队尾就是牌堆的底部。用数组 q 存牌，head 和 tail 两个指针分别指向队头和队尾。一开始把1到n依次放进队列。每次操作：先把队头的牌扔掉并输出，即 q[head++]；然后如果还有牌，就把新的队头 q[head++] 放到队尾 q[tail++]。

第三步，拿 n=7 完整走一遍。 一开始是 1 2 3 4 5 6 7：扔1、把2放到底，变成 3 4 5 6 7 2；扔3、把4放到底，变成 5 6 7 2 4；扔5、把6放到底，变成 7 2 4 6；扔7、把2放到底，变成 4 6 2；扔4、把6放到底，变成 2 6；扔2、把6放到底，变成 6；这时只剩一张6，循环结束。整个输出是 1 3 5 7 4 2 6，和样例一致。

第四步，注意循环的结束条件。 只要 head 小于 tail 就一直执行。当队列里只剩一张牌时，直接把这张牌扔出并输出，然后因为 head 等于 tail，循环自然结束。这样"每次扔掉的牌加上最后剩下的牌"就都在输出里了。输出时每个数字后面要跟一个空格。

第五步，想一想最小的 n。 题目保证 n 至少是3。当 n=3 时，一开始是 1 2 3：扔1、把2放到底，变成 3 2；扔3、把2放到底，变成 2；最后只剩2。输出是 1 3 2。可以看到，即使牌很少，我们的模拟步骤也完全一样，不会漏牌也不会出错。再想想 n 比较大的情况，比如 n=100，也只需要反复"扔一张、移一张"，程序自动循环处理，不需要人手工推导。

参考代码

// 纸牌问题：扔第一张、把新的第一张放到底部，输出扔牌顺序和最后剩的牌
#include <iostream>
using namespace std;

int main() {
    int q[205];
    int n, i;
    cin >> n;
    for (i = 0; i < n; i++) q[i] = i + 1;  // 从上到下编号1~n
    int head = 0, tail = n;
    while (head < tail) {
        // 扔出最上面的牌，每个数字后跟一个空格
        int x = q[head++];
        cout << x << " ";
        // 还剩牌时，把新的第一张放到整叠最后
        if (head < tail) {
            int y = q[head++];
            q[tail++] = y;
        }
    }
    cout << endl;
    return 0;
}

复杂度分析

n 最大为100，每张牌最多被取出一次、被放到队尾一次，总共大约2n次操作，所以时间复杂度是 O(n)。空间上数组 q 最多需要2n个格子，空间复杂度是 O(n)。