P4847 座次表（基础）

解题思路

**第一步，认识“双端队列”。**长椅可以从左边进人，也可以从右边进人，最后要按从左到右的顺序统计名单。这种“两头都能进出”的结构叫做双端队列。我们用一个大数组来模拟它，在数组的中间位置放一个“起点”，左边用head指向最左边的人，右边用tail指向最右边的下一个空位。

**第二步，分两种情况处理。**每行读入一个数字x和一个人名：如果x=0，说明这个人从左边进入长椅，那就把head往左移一格，把名字存到head这个位置；如果x=1，说明这个人从右边进入长椅，那就把名字存到tail这个位置，再把tail往右移一格。

**第三步，最后怎么输出？**题目说最后输出n行，表示长椅上从左到右的来宾名字。所以所有来宾都入场以后，我们从head开始，一直打印到tail前面一个位置，每个名字一行，就是从左到右的名单。

**第四步，注意数组的大小。**n最大是2000，全部从左边进的话，head最多往左移2000格；全部从右边进的话，tail最多往右移2000格。所以数组要留出至少4000格的空间，从正中间第2000格开始，左右都够用，我们开4005格，安全起见。

**举例子验证。**输入里 lu 和 tong 从左边进，xiong 从右边进，mei 从左边进，cheng 从右边进。最后从左到右是 mei、tong、lu、xiong、cheng，正好是样例输出。

参考代码

// P4847 座次表：双端队列，x=0从左进、x=1从右进，最后从左到右输出
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, head, tail;
char names[4005][55];
int main() {
    scanf("%d", &n);
    head = tail = 2000;  // 数组中间位置，左右两边都能扩展
    for (int i = 0; i < n; i++) {
        int x;
        char nm[55];
        scanf("%d%s", &x, nm);
        if (x == 0) {
            head--;                    // 从左边进入
            strcpy(names[head], nm);
        } else {
            strcpy(names[tail], nm);   // 从右边进入
            tail++;
        }
    }
    for (int i = head; i < tail; i++) printf("%s\n", names[i]);
    return 0;
}

复杂度分析

一共有n位来宾，每位来宾入场只是往左或往右放一个名字，时间是O(1)，最后输出再遍历一遍，所以总时间是O(n)。n最大2000，非常快。空间上需要能装下全部名字的数组，最多2000个名字，数组开4005格，绰绰有余。