P4835 排队看病（基础）

解题思路

第一步，理解"左边进"和"右边进"。 医院门口有一张长椅，病人一个接一个地来看病。医生助理会让新来的病人"从长椅的左边进去坐下"或者"从长椅的右边进去坐下"。从左边进的人会坐在长椅的最左边，从右边进的人会坐在长椅的最右边。题目要我们最后回答：长椅上从左到右坐着的人分别是谁。

第二步，用双端队列模拟长椅。 这种"两头都能进人"的数据结构叫双端队列。我们用一个很大的数组 q 来模拟长椅，把数组的中间位置当作长椅的起点。准备两个指针：head 指向长椅最左边的人，tail 指向长椅最右边的人右边的那个空位。病人从左边进时，先让 head 减1，再把名字写进 q[head]，这样新来的人就成了最左边的；病人从右边进时，把名字写进 q[tail]，然后 tail 加1，这样新来的人就成了最右边的。

第三步，举例走一遍。 样例中前三个病人都从左边进：LZZ、HSY、TSW，后进的人坐在更左边，所以这时从左到右是 TSW HSY LZZ。接着 LHS、WKA 从右边进，坐到最右边；LWJ 又从左边进，坐到最左边……最后一个 ZJX 从左边进，变成最左边的人。最后从左到右输出：ZJX ZZB LWJ TSW HSY LZZ LHS WKA HT DYL，和样例完全一致。

第四步，注意数组大小和名字的存放。 n 最大是20000，最坏情况下有一半人从左边进、一半人从右边进，长椅左右两侧各需要约20000个位置，所以我们把数组开成40005格，并且从中间第20000格开始放人，保证左边和右边都不会越界。每个人的名字用一个字符数组存，长度为105，足够装下各种名字。

参考代码

// 排队看病：病号从长椅左边或右边进入，用数组模拟双端队列输出最终顺序
#include <iostream>
using namespace std;

// 长椅上的座位，中间开始放人，左进往左、右进往右
char q[40005][105];
int head = 20000, tail = 20000;

int main() {
    int n, a, i;
    char name[105];
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> a >> name;
        if (a == 0) {           // 从左边进，坐在最左边
            head--;
            int j = 0;
            while (name[j]) { q[head][j] = name[j]; j++; }
            q[head][j] = '\0';
        } else {                // 从右边进，坐在最右边
            int j = 0;
            while (name[j]) { q[tail][j] = name[j]; j++; }
            q[tail][j] = '\0';
            tail++;
        }
    }
    // 从左到右依次输出
    for (i = head; i < tail; i++) cout << q[i] << "\n";
    return 0;
}

复杂度分析

n 最大为20000，每个病人进来时只做一次入座操作，最后从左到右输出 n 个名字，总共大约 2n 次操作，所以时间复杂度是 O(n)。空间上数组开 40005 格、每格存一个名字，空间复杂度是 O(n)。