小美和小团所在公司的食堂有N张餐桌，从左到右摆成一排，每张餐桌有2张餐椅供至多2人用餐，公司职员排队进入食堂用餐。小美发现职员用餐的一个规律并告诉小团：当男职员进入食堂时，他会优先选择已经坐有1人的餐桌用餐，只有当每张餐桌要么空着要么坐满2人时，他才会考虑空着的餐桌；
当女职员进入食堂时，她会优先选择未坐人的餐桌用餐，只有当每张餐桌都坐有至少1人时，她才会考虑已经坐有1人的餐桌；
第一行输入一个整数T（1<=T<=10），表示数据组数。
每组数据占四行，第一行输入一个整数N（1<=N<=500000）；
第二行输入一个长度为N且仅包含数字0、1、2的字符串，第i个数字表示左起第i张餐桌已坐有的用餐人数；
第三行输入一个整数M（1<=M<=2N且保证排队的每个人进入食堂时都有可供选择的餐桌）；
第四行输入一个长度为M且仅包含字母M、F的字符串，若第i个字母为M，则排在第i的人为男性，否则其为女性。
每组数据输出占M行，第i行输出一个整数j（1<=j<=N），表示排在第i的人将选择左起第j张餐桌用餐。
1 5 01102 6 MFMMFF
2 1 1 3 4 4
小记一下
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());
}
}
}*/
}
}
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int T = scan.nextInt();
while (T-- > 0) {
int n = scan.nextInt();
String tables = scan.next();
int m = scan.nextInt();
String queue = scan.next();
//队列保存 0 的位置，小根堆保存 1 的位置
Queue<Integer> zero = new ArrayDeque<>();
PriorityQueue<Integer> one = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
char num = tables.charAt(i);
if (num == '0') {
zero.offer(i);
} else if (num == '1') {
one.offer(i);
}
}
for (int i = 0; i < m; i++) {
char gen = queue.charAt(i);
int ans = 0;
if (gen == 'M') {
if (one.isEmpty()) {
ans = zero.poll();
one.offer(ans);
} else {
ans = one.poll();
}
} else {
if (zero.isEmpty()) {
ans = one.poll();
} else {
ans = zero.poll();
one.offer(ans);
}
}
System.out.println(ans+1);
}
}
}
} 只过了10个，为啥子
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.TimeoutException;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
int T = Integer.parseInt(reader.readLine());
while (T-- > 0){
int n = Integer.parseInt(reader.readLine().trim()); // 餐桌数
String strN = reader.readLine(); // 每张餐桌使用人数
int m = Integer.parseInt(reader.readLine().trim()); // 食堂排队人数
String gender = reader.readLine(); // 排队人的性别
int[] mbArr = new int[m]; // 目标输出数组
int[] czN = new int[n]; // 餐桌使用人数数组，最小值0最大值为2，0表示当前改餐桌没人使用，2表示当前改餐桌满了\
List<Integer> zeroList = new ArrayList<>(); // 存放无人餐桌的索引
List<Integer> oneList = new ArrayList<>(); // 存放1人餐桌的索引
// 01102
for (int i = 0; i < n; i++) {
// czN[i] = Integer.parseInt(String.valueOf(strN.charAt(i)));
if (Integer.parseInt(String.valueOf(strN.charAt(i))) == 0){
zeroList.add(i+1);
}
if (Integer.parseInt(String.valueOf(strN.charAt(i))) == 1){
oneList.add(i+1);
}
}
// 当男职员进入食堂时，他会优先选择已经坐有1人的餐桌用餐，只有当每张餐桌要么空着要么坐满2人时，他才会考虑空着的餐桌；
//当女职员进入食堂时，她会优先选择未坐人的餐桌用餐，只有当每张餐桌都坐有至少1人时，她才会考虑已经坐有1人的餐桌；
for (int i = 0; i < m; i++) {
char sex = gender.charAt(i); // 当前人的性别
mbArr[i] = Main.getIndex(sex, zeroList,oneList);
// System.out.println(mbArr[i]);
writer.write(Integer.toString(mbArr[i]));
writer.newLine();
}
}
writer.flush();
}
private static int getIndex(char sex, List<Integer> zeroList, List<Integer> oneList) {
Integer index = oneList.size()>0 ? oneList.get(0) : 0;
Integer index0 = zeroList.size() > 0 ? zeroList.get(0) : 0;
// 当前第一个为男性
if (sex == 'M') {
// 查看oneList中是否有值有则直接取无则去0中找
if (index > 0){
oneList.remove(0);
return index;
}else {
// 1中没有则取0中取数据并将取的数据移除加入1中
zeroList.remove(0);
oneList.add(index0);
Collections.sort(oneList);
return index0;
}
}else {
// 当前排队的为女性
if (index0 > 0){
zeroList.remove(0);
oneList.add(index0);
Collections.sort(oneList);
return index0;
}else {
// 1中没有则取0中取数据并将取的数据移除加入1中
oneList.remove(0);
return index;
}
}
}
}
一直超时，老师们怎么优化
import java.util.*;
public class Main{
public static void F(int N,int[] seats,int M,char[] waiting){
//存储<剩余座位，位置编号>映射
PriorityQueue<Integer>[] pqs=new PriorityQueue[3];
for(int i=0;i<3;i++){
pqs[i]=new PriorityQueue<Integer>();
}
for(int i=0;i<N;i++){
pqs[seats[i]].add(i+1);
}
//依次遍历当前在等待的人，选出座位
for(int i=0;i<M;i++){
char c=waiting[i];
int key1=-1,key2=-1;
if(c=='M'){
//是男人，优先选有1人的，否则选有0人的
if(!pqs[1].isEmpty()){
key1=1;
key2=2;
}else{
key1=0;
key2=1;
}
}else{
//是女人，优先选有0人的，否则选1人的
if(!pqs[0].isEmpty()){
key1=0;
key2=1;
}else{
key1=1;
key2=2;
}
}
int pos=pqs[key1].poll();
System.out.println(pos);
pqs[key2].add(pos);
}
}
public static void main(String args[]){
Scanner s=new Scanner(System.in);
//T为数据组数
int T=s.nextInt();
for(int i=0;i<T;i++){
//N为座位数
int N=s.nextInt();
char[] temp=s.next().toCharArray();
//seats为座位状态
int[] seats=new int[N];
for(int j=0;j<N;j++){
seats[j]=temp[j]-48;
}
//M为当前在排队的人数
int M=s.nextInt();
//temp2为排队人的性别
char[] temp2=s.next().toCharArray();
F(N,seats,M,temp2);
}
}
}
import java.util.Scanner;
public class Main{
public static void main(String args[]){
int N;//桌子数
int M;//人数
Scanner scan =new Scanner(System.in);
N=scan.nextInt();
StringBuffer state=new StringBuffer(N);
for(int i=0;i<N;i++){
state.append(scan.next().charAt(0));
}
M=scan.nextInt();
StringBuffer sex=new StringBuffer(M);
for(int i=0;i<M;i++){
sex.append(scan.next().charAt(0));
}
StringBuffer result=choosePos(N,M,sex,state);
for(int i=0;i<M;i++){
int num=(int)result.charAt(i)-(int)'0';
System.out.println(num);
}
}
public static StringBuffer choosePos(int N,int M,StringBuffer sex1,StringBuffer state1) {
StringBuffer result=new StringBuffer(M);
for(int i=0;i<M;i++){
if(sex1.charAt(i)=='M'){
boolean flag=true;
for(int j=0;j<N;j++){
if(state1.charAt(j)=='1'){
result.append(j+1);
state1.setCharAt(j,'2');
flag=false;
break;
}
}
if(flag){
for(int j=0;j<N;j++){
if(state1.charAt(j)=='0'){
result.append(j+1);
state1.setCharAt(j,'1');
break;
}
}
}
}else{
boolean flag=true;
for(int j=0;j<N;j++){
if(state1.charAt(j)=='0'){
result.append(j+1);
state1.setCharAt(j,'1');
flag=false;
break;
}
}
if(flag){
for(int j=0;j<N;j++){
if(state1.charAt(j)=='1'){
result.append(j+1);
state1.setCharAt(j,'2');
break;
}
}
}
}
}
return result;
}
} 
import java.util.Scanner;
public class Main{
public static void main(String[] args){
String one="1";
String o="0";
Scanner sc=new Scanner(System.in);
int arrSize=sc.nextInt();
int a;
String chi;
int b;
String sex;
char[] c;
char[] s;
for(int i=0;i<arrSize;i++){
a=sc.nextInt();
chi=sc.next();
b=sc.nextInt();
sex=sc.next();
c=chi.toCharArray();
s=sex.toCharArray();
for(int j=0;j<b;j++){
chi =(s[j]=='M')?go(one,o,chi,c):go(o,one,chi,c);
}
}
}
public static String go(String a,String b,String chi,char[] c){
int go = chi.indexOf(a);
if(go>-1){
System.out.println(go+1);
c[go]+=1;
return new String(c);
}
go= chi.indexOf(String.valueOf(b));
System.out.println(go+1);
c[go]++;
return new String(c);
}
} 实在是想不出怎么优化了， 一直超时
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
