P4844 密室逃脱（基础）

解题思路

**第一步，把扑克牌看成一列队伍。**题目说第一张牌拿走，第二张牌挪到剩余扑克牌的最后，这个动作和“从队头拿一张、再让队头下一张绕到队尾”是一模一样的。我们把n张扑克牌按顺序放进一个队列里。

**第二步，按规则操作。**每次先拿走队头那张牌，把它作为密码的一位输出；然后检查队列里还有没有牌，如果有，就把现在的队头那张牌挪到队尾去。这样重复，直到所有牌都被拿走。

**第三步，扑克牌是字符串，要小心。**扑克牌可能是 A、2、3……9、J、Q、K，甚至样例里还有“1”。所以不能用数字，要用字符数组来存每一张牌。挪到队尾时，要把这个字符串的每个字符都拷贝过去，再补上结束符。

**第四步，注意人数变少的情况。**每拿走一张牌、再挪一张牌，队伍会越来越短。当队列里只剩最后一张牌时，把它拿走就可以结束了，这时候没有第二张牌可以挪，直接停止。

**举例子验证。**输入 10 张牌 A A J 1 2 K 3 7 Q 6：第一步拿走A，把下一张A挪到队尾；第二步拿走J，把1挪到队尾……最后拿走的顺序是 A J 2 3 Q A K 6 7 1，和样例输出一模一样。

参考代码

// P4844 密室逃脱：拿走第1张输出，第2张挪到剩余扑克牌的最后
#include <iostream>
#include <cstdio>
using namespace std;
int n;
char q[105][5];
int h, t;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%s", q[t++]);  // 扑克牌入队
    int first = 1;
    while (h < t) {
        if (!first) printf(" ");
        first = 0;
        printf("%s", q[h++]);        // 拿走第一张输出
        if (h < t) {                 // 第二张挪到末尾
            int k = 0;
            while (q[h][k]) { q[t][k] = q[h][k]; k++; }
            q[t][k] = '\0';
            t++;
            h++;
        }
    }
    printf("\n");
    return 0;
}

复杂度分析

每张牌被拿走一次、最多被挪动一次，一共n张牌，所以时间是O(n)。每张牌是一个长度不超过2的字符串，拷贝它是常数时间，可以认为每步都是O(1)。n最大不到50，程序一瞬间就出结果。空间上需要一个能存下所有牌和“挪到队尾”的牌的数组，约O(n)。