题解 | #公司食堂#
公司食堂
http://www.nowcoder.com/questionTerminal/601815bea5544f389bcd20fb5ebca6a8
和其他的解题稍有不同, 空桌位无需使用小顶堆,只需维护一个list即可,每次poll第一个即可
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String T = in.nextLine();
for (int i = 0; i < Integer.parseInt(T); i++) {
String N = in.nextLine();
String nStr = in.nextLine();
String M = in.nextLine();
String mStr = in.nextLine();
solve(Integer.parseInt(N), nStr, Integer.parseInt(M), mStr);
}
}
public static void solve(int n, String nStr, int m, String mStr) {
LinkedList<Integer> zero = new LinkedList<>();
PriorityQueue<Integer> one = new PriorityQueue<>();
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) {
char ch = nStr.charAt(i-1);
if (ch == '0') {
zero.add(i);
} else if (ch == '1') {
one.add(i);
}
}
byte[] input = mStr.getBytes();
for (byte sex : input) {
if (sex == 'M') {
if (one.size() > 0) {
sb.append(one.poll()+"\n");
} else {
int i = zero.poll();
sb.append(i + "\n");
one.add(i);
}
}else {
if(zero.size() >0){
int i = zero.poll();
sb.append( i + "\n");
one.add(i);
}else {
sb.append(one.poll()+"\n");
}
}
}
System.out.print(sb.toString());
}
}