P4854 字母排排站（入门）

解题思路

第一步，理解题意。 10 个字母站成一排，按下面的规则组成新的序列：每轮先把第 1 个字母移动到最右端，然后把新的第 1 个字母（也就是原来的第 2 个字母）删除。被删除的字母按顺序排起来，就是新的序列。

第二步，类比游戏。 这就像 10 个小朋友排队：队头的小朋友先跑到队伍最后面，然后新的队头第二个小朋友被请出队伍。一直重复，直到队伍里所有人都被请出。请出顺序就是答案。

第三步，用队列模拟。 用数组 q 当队列，head 指向队首，tail 指向队尾的下一个空位。初始把 10 个字母按顺序放进 q[0] 到 q[9]，head=0、tail=10。

第四步，按规则循环。 每轮做两件事：先移动，把队首字母放到队尾，即 q[tail]=q[head]，然后 head 和 tail 都加 1；再删除，输出现在的队首 q[head]，然后 head 加 1。一直循环到 head 等于 tail，队伍就空了。

第五步，注意边界。 当队伍只剩最后一个字母时，把它"移到末尾"其实就是还是它自己，然后删除，循环自然结束。由于移动会让 tail 不断变大，数组要开大一点（开 50 保险），防止越界。举个例子：ABCDEFGHIJ，第一轮把 A 移到末尾、删除 B，第二轮把 C 移到末尾、删除 D……最后删除顺序是 B D F H J C G A I E，连起来就是 BDFHJCGAIE，和样例一致。

参考代码

// 字母排排站：第1个字母移到末尾，第2个删除，删除的组成新序列
#include <iostream>
using namespace std;
int main() {
    char s[15];
    cin >> s;
    int q[50];            // 队列
    int n = 10;
    for (int i = 0; i < n; i++) q[i] = s[i];
    int head = 0, tail = n;
    while (head < tail) {
        q[tail++] = q[head];  // 第1个字母移到最右端
        head++;
        cout << (char)q[head]; // 删除第2个字母并输出
        head++;
    }
    cout << endl;
    return 0;
}

复杂度分析

时间复杂度：10 个字母，每轮操作固定，总共执行约 10 轮，所以是 O(10) 的常数时间。

空间复杂度：队列数组大小固定为 50，是 O(1) 的常数空间。