题解 | #公司食堂#

小记一下 List+ TreeSet超时 List+ PriorityQueue 超时

数组模拟+双指针 超时 最后发现是卡的输入输出

坑点：writer.flush 最后一次刷新输出写一次刷新一次只能过11个点

数组模拟+双指针 o(n) 版本如下

import java.util.Arrays;
import java.util.Scanner;
import java.io.*;
// hashset 数组 保证数据单一性的数组 查找元素快 （哈希表hashmap实现）
// treeset 数组 排序的数组 红黑树维护元素的顺序
// hashmap 
// treemap 排序 按照key 值排序 不按照value 红黑树
// 优先队列 ？ + list ？ || + hashmap ？
// sortedset
// java 的快速输入输出 
public class Main {
    public static void main(String[] args) throws Exception{
         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
         BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
         int t = Integer.parseInt(reader.readLine());
        String desk;
        String s = null;
        int[][] desks = new int[2][500000 + 5];
        int[] other = new int[500000 + 5];        
            while (t != 0) {
                Arrays.fill(desks[0],0);
                Arrays.fill(desks[1],0);
                Arrays.fill(other,0);
                t--;
                int n;
                n = Integer.parseInt(reader.readLine());
                int x;
                desk = reader.readLine();
                int cnt1 = 0;
                int cnt0 = 0;
                for (int i = 1; i <= n; i++) {
                    x = Integer.parseInt(desk.charAt(i - 1) + "");
                    if (x != 2) {
//                      list.get(x).add(i);
                        if (x == 1) {
                            desks[1][cnt1++] = i;
                        } else {
                            desks[0][cnt0++] = i;
                        }
                    }
                }
                int m;
                m = Integer.parseInt(reader.readLine());
                s = reader.readLine();
                int to = s.length();
                int index1 = 0, index0 = 0;
                int indexother = 0;
                int cntother = 0;
                int ans = 0;
                for (int i = 0; i < to; i++) {
                    if (s.charAt(i) == 'M') {
                        if (other[indexother] != 0 || desks[1][index1] != 0) {
                            if (desks[1][index1] == 0) {
                                ans = other[indexother++];
                            } else if (other[indexother] == 0) {
                                ans = desks[1][index1++];
                            } else {
                                 if (desks[1][index1] < other[indexother]) {
                                     ans = desks[1][index1++];
                                  }  else {
                                      ans = other[indexother++];
                                  }                                
                            }
                        }else {
                            if (index0 != cnt0) {
                                other[cntother++] = desks[0][index0];
                                ans = desks[0][index0++];
                            } 
                        }
//                        System.out.println(ans);
                          writer.write(Integer.toString(ans));
                          writer.newLine();
                       //   writer.flush();
                      //    writer.newLine();
                    } else {
                        if (index0 != cnt0) {
                            other[cntother++] = desks[0][index0];
                            ans = desks[0][index0++];
                        } else {
                            if (other[indexother] != 0 || desks[1][index1] != 0) {
                                if (desks[1][index1] == 0) {
                                    ans = other[indexother++];
                                } else if (other[indexother] == 0) {
                                    ans = desks[1][index1++];
                                } else {
                                     if (desks[1][index1] < other[indexother]) {
                                         ans = desks[1][index1++];
                                      }  else {
                                          ans = other[indexother++];
                                      }
//                             
                                }
                            }
                        }
                        writer.write(Integer.toString(ans));
                        writer.newLine();
                       // writer.flush();
                       // writer.newLine();
                    }
                }
                writer.flush();
                // 优先队列 版本
                /*
                for (int i = 0; i < to; i++) {
                    if (s.charAt(i) == 'M') {
                        if (list.get(1).size() != 0) {
                            System.out.println(list.get(1).poll());
                        } else if (list.get(0).size() != 0) {
                            System.out.println(list.get(0).peek());
                            list.get(1).offer(list.get(0).poll());
                        }
                    } else {
                        if (list.get(0).size() != 0) {
                            System.out.println(list.get(0).peek());
                            list.get(1).offer(list.get(0).poll());
                        } else if (list.get(1).size() != 0) {
                            System.out.println(list.get(1).poll());
                        }
                    }
                }*/
        }
    }
}