P4834 排队问题（入门）

解题思路

第一步，看懂游戏规则。 有 n 个人排成一队，从左到右按照"1、2、1、2……"的顺序报数。报到数字1的人立刻出列，离开队伍；报到数字2的人不出列，而是立刻跑到队伍的最右边重新排队。报完一轮之后又从队伍最左边开始，继续"1、2、1、2"地报数，一直重复，直到所有人都出列为止。题目要我们输出每个人出列的顺序。

第二步，用队列来模拟这个队伍。 队列的特点是"先进先出"，队头出、队尾进，正好和题目中"从左边出列、到右边排队"的过程一致。我们用数组 q 存放队伍，用两个下标 head 和 tail 分别指向队头和队尾。每次从队头取出一个人，就是 q[head]，然后 head 加1。

第三步，用变量控制报数。 准备一个变量 c，表示"这次该报到几"，它只在1和2之间切换。每次从队头取出一个人 x：如果 c 等于1，这个人出列，直接输出它的编号，然后把 c 改成2；如果 c 等于2，这个人不出列，而是把它放到队尾，也就是执行 q[tail++]=x，然后把 c 改成1。这样反复执行，直到 head 等于 tail，队伍空了为止。

第四步，拿样例验证一遍。 队伍是 1 2 3 4 5 6 7 8：1报到1出列，2报到2跑到队尾，3报到1出列，4报到2跑到队尾……依次下去，出列顺序正好是 1 3 5 7 2 6 4 8，和题目给出的样例一模一样。注意输出时每个编号之间用一个空格隔开。

第五步，考虑数组大小。 n 最大是100，每个人最多被移到队尾一次，所以队列长度最多到 2n 左右，数组开205个格子就足够用了。

参考代码

// 排队问题：1、2、1、2报数，报1出列，报2到队尾，模拟出列顺序
#include <iostream>
using namespace std;

int main() {
    int q[205];
    int n, i;
    cin >> n;
    for (i = 0; i < n; i++) cin >> q[i];
    int head = 0, tail = n;  // 队头、队尾指针
    int c = 1;               // 当前报的数，1或2
    bool first = true;
    while (head < tail) {
        int x = q[head++];   // 队头出队
        if (c == 1) {        // 报到1，出列
            if (!first) cout << " ";
            first = false;
            cout << x;
            c = 2;
        } else {             // 报到2，移到队尾
            q[tail++] = x;
            c = 1;
        }
    }
    cout << endl;
    return 0;
}

复杂度分析

n 最大为100，每个人在队伍中最多被取出一次，也最多被移到队尾一次，总共操作不超过 2n 次，所以时间复杂度是 O(n)。空间上数组 q 最多需要 2n 个格子，空间复杂度也是 O(n)。