题解 | #公司食堂#

思路是用minheap来储存人数为0和1的桌子。这样对于每个人，可实现O(logn)获取下张可用的桌子。 总时间复杂度为O(logN)。 Note:数据量过大时，在输出结果的时候，如果每次都用System.out.println则会花费大量的时间，可能会造成超时。解决方法是用String Builder先获取总的输出字符串，最后输出这个字符串。

import java.util.Scanner;
import java.util.Queue;
import java.util.PriorityQueue;

class Person{
    int pos;
    boolean isMale;
    Person(int p, boolean m){
        pos = p;
        isMale = m;
    }
}

public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int tableCount = 0;
        int personCount = 0;
        
        Person[] person = null;
        int[] table = null;        
        
        
        for(int i = 0; i < n; i++){
            tableCount = scan.nextInt();
            table = new int[tableCount];
            String tmp = scan.next();
            char[] tmpArr = tmp.trim().toCharArray();
            for(int j = 0; j < tableCount; j++){
                //System.out.print(j);
                table[j] = tmpArr[j] - '0';
            }
            personCount = scan.nextInt();
            person = new Person[personCount];
            tmp = scan.next();
            tmpArr = tmp.trim().toCharArray();
            for(int j = 0; j < personCount; j++){
                person[j] = new Person(j, tmpArr[j]=='M');
            }
            findPos(table, person);
            StringBuilder strb = new StringBuilder();
            for(int j = 0; j < personCount; j++){
                strb.append(person[j].pos + 1 + "\n");
                
            }
            strb.deleteCharAt(strb.length() - 1);
            System.out.println(strb.toString());
        }
        
        
    
    }
    
    public static void findPos(int[] table, Person[] person){
        Queue<Integer> emptyPos = new PriorityQueue<>();
        Queue<Integer> onePos = new PriorityQueue<>();
        for(int i = 0; i < table.length; i++){
            if(table[i] == 0) {
            	emptyPos.offer(i);
            } 
            else if(table[i] == 1) onePos.offer(i);
        }
        
        for(int i = 0; i < person.length; i++){
            if(person[i].isMale){
                int pos = 0;
                if(onePos.size() > 0){
                    person[i].pos = onePos.poll();
                    
                }
                else{
                    pos = emptyPos.poll();
                    person[i].pos = pos;
                    onePos.offer(pos);
                }
            }
            else{
                int pos = 0;
                if(emptyPos.size() > 0){
                    pos = emptyPos.poll();
                    onePos.offer(pos);
                    person[i].pos = pos;
                }
                else{
                    person[i].pos = onePos.poll();
                }
            }
        }
    }
}