P4840 童童去存款（基础）

解题思路

**第一步，想想银行窗口是怎么工作的。**银行里有两个窗口：A窗口速度是B窗口的2倍，也就是说A窗口处理完2个顾客的时间里，B窗口只处理完1个顾客。所以我们可以把时间分成一小段一小段，每一段里A窗口完成2个人、B窗口完成1个人。如果两个窗口同时完成，A窗口的顾客先出来。

**第二步，怎么安排顾客排队？**题目规定：编号是奇数的顾客去A窗口，编号是偶数的顾客去B窗口。我们就用两个队列分别存放他们，一个叫A队，一个叫B队。队头（ha、hb）表示下一个要处理的人，队尾（ta、tb）表示新来的人排在哪里。

**第三步，按照一轮一轮输出。**每一轮先看A队：从队头连续处理2个顾客（如果A队还有人的话），边处理边输出；再处理B队队头的1个顾客并输出。这样一轮一轮做下去，直到两个队都空了，就得到了完整的完成顺序。

**第四步，想一想边界情况。**如果A队只剩下1个人，而B队还有很多人，那么这一轮A队只处理这1个人，B队还是处理1个，下一轮A队没人的话就直接处理B队。比如样例中A队有6个人、B队有2个人，最后一轮A队输出13和15后，B队已经没人了，游戏结束。

**举一个具体的例子。**输入是 8 2 1 3 9 4 11 13 15：奇数是1、3、9、11、13、15，偶数是2、4。第一轮A队出1、3，B队出2；第二轮A队出9、11，B队出4；第三轮A队出13、15，B队空了。合起来就是 1 3 2 9 11 4 13 15，和样例一模一样。

参考代码

// P4840 童童去存款：奇数去A窗口(每轮2个)，偶数去B窗口(每轮1个)，同轮A先输出
#include <iostream>
#include <cstdio>
using namespace std;
int n, num;
int qa[1005], qb[1005];
int ha, ta, hb, tb;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        if (num % 2) qa[ta++] = num;  // 奇数进A窗口队列
        else qb[tb++] = num;          // 偶数进B窗口队列
    }
    int first = 1;
    while (ha < ta || hb < tb) {
        for (int i = 0; i < 2 && ha < ta; i++) {  // A窗口每轮处理2个
            if (!first) printf(" ");
            first = 0;
            printf("%d", qa[ha++]);
        }
        if (hb < tb) {  // B窗口每轮处理1个
            if (!first) printf(" ");
            first = 0;
            printf("%d", qb[hb++]);
        }
    }
    printf("\n");
    return 0;
}

复杂度分析

把每个顾客分成奇数、偶数各入队一次，输出时每个人也只被处理一次，所以总时间是O(N)，其中N是顾客总数（N≤1000）。数组只需要存下所有顾客，空间也是O(N)。这个题目其实就是模拟两个速度不同的窗口，代码很直接。