题解 | #公司食堂#

一开始用的两个小根堆存人数为0和1的座位，后来想想用三个LinkedList就可以了，一个存放一开始人数为0的座位，一个存放一开始人数为1的座位，还有一个存放人数由0变为1的座位，需要查找人数为1的座位时，比较后两个List的首元素大小，如果其中一个为空，就选择另外一个。 其实这题考的是IO的处理吧，看了评论区题解才知道用Scanner会超时，尽量使用缓冲字符流。

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            int N = Integer.parseInt(br.readLine());
            String seat = br.readLine();
            int M = Integer.parseInt(br.readLine());
            String sex = br.readLine();
            List<Integer> zero = new LinkedList<>();
            List<Integer> one = new LinkedList<>();
            List<Integer> zeroToOne = new LinkedList<>();
            for (int i = 0; i < N; i++) {
                if (seat.charAt(i) == '0') {
                    zero.add(i);
                } else if (seat.charAt(i) == '1') {
                    one.add(i);
                }
            }
            for (int i = 0; i < M; i++) {
                int index = 0;
                if (sex.charAt(i) == 'M') {
                    if (!one.isEmpty() || !zeroToOne.isEmpty()) {
                        if (zeroToOne.isEmpty() || (!one.isEmpty() && one.get(0) < zeroToOne.get(0))) {
                            index = one.remove(0);
                        } else {
                            index = zeroToOne.remove(0);
                        }
                    } else {
                        index = zero.remove(0);
                        zeroToOne.add(index);
                    }
                } else {
                    if (!zero.isEmpty()) {
                        index = zero.remove(0);
                        zeroToOne.add(index);
                    } else {
                        if (zeroToOne.isEmpty() || (!one.isEmpty() && one.get(0) < zeroToOne.get(0))) {
                            index = one.remove(0);
                        } else {
                            index = zeroToOne.remove(0);
                        }
                    }
                }
                bw.write(String.valueOf(index + 1));
                bw.newLine();
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
}