小美和小团所在公司的食堂有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
使用三个小根堆，分别存储当前人数为0,1,2的三种桌子的桌号，记为pq0,pq1,pq2
以男职员为例：
因为桌号存储在优先队列，所以堆顶的桌号总是最小的，保证每个人有多个选择时优先坐最左边的桌子。
女职员同理。
时间复杂度：O(MLogN)
输入输出用BufferedReader和BufferedWriter才能过，用System.out.println会超时。
import java.io.*;
import java.util.*;
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());
for (int i = 0; i < T; i++) {
int N = Integer.parseInt(reader.readLine());
String tables = reader.readLine();
int M = Integer.parseInt(reader.readLine());
String enters = reader.readLine();
int[] res = solve(tables, enters);
for (int r : res) {
writer.write(Integer.toString(r));
writer.newLine();
}
}
writer.flush();
}
private static int[] solve(String tables, String enters) {
List<PriorityQueue<Integer>> pqs = new ArrayList<>(3);
pqs.add(new PriorityQueue<>());
pqs.add(new PriorityQueue<>());
pqs.add(new PriorityQueue<>());
for (int i = 0; i < tables.length(); i++) {
pqs.get(tables.charAt(i) - '0').add(i);
}
int[] res = new int[enters.length()];
for (int i = 0; i < enters.length(); i++) {
int table;
if (enters.charAt(i) == 'M') {
if (pqs.get(1).isEmpty()) {
table = pqs.get(0).poll();
pqs.get(1).add(table);
} else {
table = pqs.get(1).poll();
pqs.get(2).add(table);
}
} else {
if (!pqs.get(0).isEmpty()) {
table = pqs.get(0).poll();
pqs.get(1).add(table);
} else {
table = pqs.get(1).poll();
pqs.get(2).add(table);
}
}
res[i] = table + 1;
}
return res;
}
}
import heapq T = int(input()) while T: T -= 1 N = int(input()) people = input() M = int(input()) genders = input() people = [int(x) for x in people] heap0 = [] heap1 = [] for i, person in enumerate(people, start=1): if person == 0: heapq.heappush(heap0, i) if person == 1: heapq.heappush(heap1, i) for gender in genders: f0 = heap0[0] if heap0 else 0 f1 = heap1[0] if heap1 else 0 if gender == 'M': ans = 'f1' if f1 else 'f0' else: ans = 'f0' if f0 else 'f1' if ans == 'f1': heapq.heappop(heap1) print(f1) else: heapq.heappush(heap1, heapq.heappop(heap0)) print(f0)
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int n, num;
cin >> n;
string table, people;
cin >> table;
cin >> num;
cin >> people;
//vector<vector<int>> mp(3);
priority_queue<int, vector<int>, greater<int>> mp0, mp1;
for (int i = 0; i < n; ++i) {
//mp[table[i] - '0'].emplace_back(i + 1);
int tmp = table[i] - '0';
if (tmp == 0) {
mp0.push(i + 1);
} else if (tmp == 1) {
mp1.push(i + 1);
}
}
for (auto& c : people) {
if (c == 'F') {
if (!mp0.empty()) {
int res = mp0.top();
mp0.pop();
mp1.push(res);
cout << res << '\n';
} else {
int res = mp1.top();
mp1.pop();
cout << res << '\n';
}
} else {
if (!mp1.empty()) {
int res = mp1.top();
mp1.pop();
cout << res << '\n';
} else {
int res = mp0.top();
mp0.pop();
mp1.push(res);
cout << res << '\n';
}
}
}
}
return 0;
} 
#include<bits/stdc++.h>
using namespace std;
int main() {
//freopen("test.txt", "r", stdin);
int T = 0;
cin >> T;
for (int k = 0;k < T;++k) {
int N, M;
cin >> N;
string desk, que;
cin >> desk;
cin >> M;
cin >> que;
int f_zero = -1, f_one = -1;
for (int i = 0;i < N;++i) {
if (f_zero != -1 && f_one != -1) break;
else if (f_zero == -1 && desk[i] == '0') f_zero = i;
else if (f_one == -1 && desk[i] == '1') f_one = i;
}
for (int i = 0;i < M;++i) {
if (que[i] == 'M') {
if (f_one < N) {
printf("%d\n", f_one + 1);
desk[f_one] = '2';
while (f_one < N && desk[f_one] != '1') f_one++;
}
else {
printf("%d\n", f_zero + 1);
desk[f_zero] = '1';
if (f_zero < f_one) f_one = f_zero;
while (f_zero < N && desk[f_zero] != '0') f_zero++;
}
}
else {
if (f_zero < N) {
printf("%d\n", f_zero + 1);
desk[f_zero] = '1';
if (f_zero < f_one) f_one = f_zero;
while (f_zero < N && desk[f_zero] != '0') f_zero++;
}
else {
printf("%d\n", f_one + 1);
desk[f_one] = '2';
while (f_one < N && desk[f_one] != '1') f_one++;
}
}
}
}
return 0;
} 
import java.io.BufferedInputStream;
import java.util.Scanner;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
try (Scanner sc = new Scanner(new BufferedInputStream(System.in))) {
int T = sc.nextInt();
while (T-- > 0) method(sc.nextInt(), sc.next(), sc.nextInt(), sc.next());
}
}
public static void method(int N, String ns, int M, String ms) {
TreeSet<Integer> d0 = new TreeSet<>();
TreeSet<Integer> d1 = new TreeSet<>();
for (int i = 1; i <= N; i++) {
switch (ns.charAt(i - 1)) {
case '0':
d0.add(i);
break;
case '1':
d1.add(i);
break;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < M; i++) {
Integer first;
if ('M' == ms.charAt(i)) {
if (d1.isEmpty()) {
first = d0.first();
d0.remove(first);
d1.add(first);
} else {
first = d1.first();
d1.remove(first);
}
} else {
if (d0.isEmpty()) {
first = d1.first();
d1.remove(first);
} else {
first = d0.first();
d0.remove(first);
d1.add(first);
}
}
sb.append(first).append("\n");
}
System.out.print(sb);
}
} 
#include<bits/stdc++.h>
using namespace std;
int main()
{
int group;
cin>>group;
while(group--)
{
int table_num,person_num;
string table_person,sex;
cin>>table_num>>table_person
>>person_num>>sex;
priority_queue<int,vector<int>,greater<int> >mp0,mp1;
for(int i=0; i<table_num; i++)
{
if(table_person[i]=='0')
mp0.push(i+1);
else if(table_person[i]=='1')
mp1.push(i+1);
}
for(int j=0;j<person_num;j++)
{
if(sex[j]=='M')
{
if(!mp1.empty())
{
int temp=mp1.top();
mp1.pop();
cout<<temp<<'\n';
}
else{
int temp = mp0.top();
mp0.pop();
cout<<temp<<'\n';
mp1.push(temp);
}
}
else
{
if(!mp0.empty())
{
int temp = mp0.top();
mp0.pop();
cout<<temp<<'\n';
mp1.push(temp);
}
else
{
int temp=mp1.top();
mp1.pop();
cout<<temp<<'\n';
}
}
}
}
return 0;
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.PriorityQueue;
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().trim());
while(T-- > 0){
int n = Integer.parseInt(br.readLine().trim());
char[] status = br.readLine().trim().toCharArray();
int m = Integer.parseInt(br.readLine().trim());
char[] queue = br.readLine().trim().toCharArray();
// 准备两个队列分别放置空餐桌和已经坐了一人的餐桌
ArrayList<PriorityQueue<Integer>> queueList = new ArrayList<>();
queueList.add(new PriorityQueue<Integer>());
queueList.add(new PriorityQueue<Integer>());
// 将n个餐桌加入队列
for(int i = 0; i < n; i++)
if(status[i] - '0' < 2) queueList.get(status[i] - '0').offer(i + 1);
int idx;
for(int i = 0; i < m; i++){
if(queue[i] == 'M'){
if(!queueList.get(1).isEmpty()){
// 坐着一个人的餐桌还有，就出队
idx = queueList.get(1).poll();
bw.write(idx + "\n");
bw.flush();
}else{
// 否则只能坐空桌
idx = queueList.get(0).poll();
bw.write(idx + "\n");
bw.flush();
// 坐完之后还要将这个桌加入人数为1的队列
queueList.get(1).offer(idx);
}
}else{
if(!queueList.get(0).isEmpty()){
// 空桌还有，就出队
idx = queueList.get(0).poll();
bw.write(idx + "\n");
bw.flush();
// 坐完之后还要将这个桌加入人数为1的队列
queueList.get(1).offer(idx);
}else{
// 否则就坐已经有一人就餐的餐桌
idx = queueList.get(1).poll();
bw.write(idx + "\n");
bw.flush();
}
}
}
}
}
} 
#include<bits/stdc++.h>
using namespace std;
int main(){
int groups = 0;
cin >> groups;
while(groups > 0){
groups--;
int n;
cin >> n;
vector<int>p1;
vector<int>p2;
char str[n+1];
scanf("%s",str);
for(int i = 1;i <= n;i++){
char c= str[i-1];
if(c == '0'){
p1.push_back(i);
}
else if(c == '1'){
p2.push_back(i);
}
}
int j = 0;
int k = 0;
int z = 0;
vector<int> p3;
int m;
cin >> m;
char str1[m+1];
scanf("%s",str1);
for(int i = 0;i < m;i++){
char c= str1[i];
if(c == 'M'){
if(k < p2.size()){
if(z < p3.size() && p3[z] > p2[k]){
int cur = p2[k];
k++;
cout << cur << '\n';
}
else if(z < p3.size() && p3[z] < p2[k]){
int cur = p3[z];
z++;
cout << cur << '\n';
}
else{
int cur = p2[k];
k++;
cout << cur << '\n';
}
}
else if(z < p3.size()){
if( k < p2.size() && p3[z] > p2[k]){
int cur = p2[k];
k++;
cout << cur << '\n';
}
else if( k < p2.size() &&p3[z] < p2[k]){
int cur = p3[z];
z++;
cout << cur << '\n';
}
else{
int cur = p3[z];
z++;
cout << cur << '\n';
}
}
else {
int cur = p1[j];
j++;
cout << cur << '\n';
p3.push_back(cur);
}
}
else{
if( j < p1.size()){
int cur = p1[j];
j++;
cout << cur << '\n';
p3.push_back(cur);
}
else{
if(k >= p2.size()){
int cur = p3[z];
z++;
cout << cur << '\n';
continue;
}
if(z < p3.size() && p3[z] > p2[k]){
int cur = p2[k];
k++;
cout << cur << '\n';
}
else if(z < p3.size() && p3[z] < p2[k]){
int cur = p3[z];
z++;
cout << cur << '\n';
}
else{
int cur = p2[k];
k++;
cout << cur << '\n';
}
}
}
}
}
} 
package main
import (
"bufio"
"os"
"strconv"
"fmt"
"container/heap"
)
func main() {
sc := bufio.NewScanner(os.Stdin)
bf := make([]byte, 2000*1024)
sc.Buffer(bf, len(bf))
sc.Scan()
T, _ := strconv.Atoi(sc.Text())
for t := 0; t < T; t++ {
sc.Scan()
//N, _ := strconv.Atoi(sc.Text())
sc.Scan()
strArr := sc.Text()
sc.Scan()
//M, _ := strconv.Atoi(sc.Text())
sc.Scan()
str2 := sc.Text()
h0 := &IntHeap{}
h1 := &IntHeap{}
for i := 0; i < len(strArr); i++ {
if strArr[i] == '0' {
heap.Push(h0, i)
} else if strArr[i] == '1' {
heap.Push(h1, i)
}
}
heap.Init(h0)
heap.Init(h1)
for i := 0; i < len(str2); i++ {
x := 0
if str2[i] == 'M' {
if len(*h1) <= 0 {
x = heap.Pop(h0).(int)
heap.Push(h1, x)
} else {
x = heap.Pop(h1).(int)
}
//fmt.Println(x+1)
fmt.Print(x+1, "\n")
} else if str2[i] == 'F' {
if len(*h0) <= 0 {
x = heap.Pop(h1).(int)
} else {
x = heap.Pop(h0).(int)
heap.Push(h1, x)
}
fmt.Print(x+1, "\n")
//fmt.Println(x+1)
}
}
}
}
type IntHeap []int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h IntHeap) Swap(i ,j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() (x interface{}) {
x = (*h)[len(*h)-1]
*h = (*h)[:len(*h)-1]
return
}
1、尽量只使用一个堆，存放坐0人的桌子用数组就好2、不要使用 shift 方法，该方法时间复杂度较高（n或logn），对0人的桌子设置索引，每次占用则 索引+1，这样需要坐0人的桌子时只需访问该数组中该索引的元素
class PriorityQueue {
constructor() {
this.tree = [];
}
insert(val) {
this.tree.push(val);
this._up(this.tree.length - 1);
}
remove() {
let last = this.tree.pop();
if (this.tree.length > 0) {
this.tree[0] = last;
this._down(0);
}
}
_down(index) {
let tree = this.tree;
let last_no_leaf = ~~((tree.length - 2) / 2);
if (index > last_no_leaf) return;
while (index <= last_no_leaf) {
let l = tree[index * 2 + 1];
let r = tree[index * 2 + 2] || tree[index * 2 + 1];
let min = l <= r ? l : r;
let minIndex = l <= r ? index * 2 + 1 : index * 2 + 2
if (tree[index] > min) {
[tree[index], tree[minIndex]] = [tree[minIndex], tree[index]]
index = minIndex
} else {
return;
}
}
}
_up(index) {
let tree = this.tree;
while (index !== 0) {
let p = ~~((index - 1) / 2);
if (tree[index] < tree[p]) {
[tree[index], tree[p]] = [tree[p], tree[index]];
index = p;
} else {
return;
}
}
}
}
readline();
let result = '';
while(line = readline()){
const n = ~~line;
let ts = readline().split('');
const m = ~~readline(),
ga = readline();
let t0 = [],t1 = new PriorityQueue();
ts.forEach((e,i)=>{
if(e=='0'){
t0.push(i+1);
}else if(e=='1'){
t1.tree.push(i+1);
}
})
let index0 = 0;
for(let i =0;i<m;i++){
if((ga[i]=='M'&&t1.tree.length>0)||(ga[i]=='F'&&index0>=t0.length)){
result+=t1.tree[0]+'\n';
t1.remove();
}else{
result+=t0[index0]+'\n';
t1.insert(t0[index0]);
index0++;
}
}
}
console.log(result); 
#pragma warning(disable:4996)
#include <iostream>
#include<queue>
using namespace std;
const int N = 1e6 +10;
int n, zw, pp, d;
char xb[N];
priority_queue<int, vector<int>, greater<int>> zero, one;//小顶堆储存桌子编号
void pkone() {//坐有一人的桌
d = one.top();
cout << d << endl;
one.pop();
}
void pkzero() {//坐没人的桌子
d = zero.top();
zero.pop();
one.push(d);
cout << d << endl;
}
int main() {
int x;
cin >> n >> zw;
while (n--) {
scanf("%s", xb);
for (int i = 1; i <= zw; i++) {
if (xb[i - 1] == '0')zero.push(i);
if (xb[i - 1] == '1') one.push(i);
}
cin >> pp;
scanf("%s", xb);
for (int i = 0; i <= pp; i++) {
if (xb[i] == 'M') {
if (!one.empty()) {
pkone();
}
else {
pkzero();
}
}
if (xb[i] == 'F') {
if (!zero.empty()) {
pkzero();
}
else {
pkone();
}
}
}
}
return 0;
} 
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 groupNums = Integer.parseInt(reader.readLine());
for (int i = 0; i < groupNums; i++) {
int tableNums = Integer.parseInt(reader.readLine());
String haveSits = reader.readLine();
TreeSet<Integer> oneTables = new TreeSet<>();
TreeSet<Integer> zeroTables = new TreeSet<>();
for (int j = 0; j < tableNums; j++) {
char c = haveSits.charAt(j);
if (c == '0')
zeroTables.add(j + 1);
else if (c == '1') {
oneTables.add(j + 1);
}
}
int peopleNums = Integer.parseInt(reader.readLine());
char[] sex = reader.readLine().toCharArray();
for (int j = 0; j < peopleNums; j++) {
if (sex[j] == 'M') {
if (oneTables.size() != 0) {
Integer first = oneTables.first();
writer.write(first.toString());
writer.newLine();
// System.out.println(first);
oneTables.remove(first);
}else {
Integer table = zeroTables.first();
oneTables.add(table);
writer.write(table.toString());
writer.newLine();
// System.out.println(table);
zeroTables.remove(table);
}
} else {
if (zeroTables.size() != 0) {
Integer table = zeroTables.first();
oneTables.add(table);
writer.write(table.toString());
writer.newLine();
// System.out.println(table);
zeroTables.remove(table);
}else {
Integer first = oneTables.first();
// System.out.println(first);
writer.write(first.toString());
writer.newLine();
oneTables.remove(first);
}
}
}
writer.flush();
}
} 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
#define x first
#define y second
typedef long long ll;
const int N = 5E6 + 10;
int n, T, m;
char s[N],person[N];
int main() {
scanf("%d",&T);
while (T--) {
scanf("%d",&n);
scanf("%s",s);
scanf("%d\n%s",&m,person);
priority_queue<int, vector<int>, greater<int>>zeros;
priority_queue<int, vector<int>, greater<int>>ones;
for (int i = 1; i <= n; i++) {
int t = s[i - 1] - '0';
if (t == 2)continue;
if (t == 1)ones.push(i);
else zeros.push(i);
}
for (int i = 0; i < m; i++) {
if(person[i]=='M'&&ones.size()||person[i]=='F'&&(!zeros.size()))
{
int res=ones.top();
printf("%d\n",res);
ones.pop();
}
else
{
int res=zeros.top();
printf("%d\n",res);
zeros.pop();
ones.push(res);
}
}
}
return 0;
} 小记一下
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());
}
}
}*/
}
}
}
介绍一种O（n）的做法。
把桌子分为两类：
A类：坐人数量为0（即有两个空座），
B类：坐人数量1（一个空座）。
根据题意，A类桌子如果有人坐下，那么将会变成B类的桌子。采用贪心的思想，M必须先选B类，仅当B类没有时，才选A类。F则正相反。因此，定义三个队列q0，q1，qb：
q0：存储A类-坐人数量为0
q1：存储B类-坐人数量为1
qb：存储A类转换得到的B类
先扫描一次桌子序列，按编号升序的方式将A、B类，分别存储到q1和q0队列中。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int f0,r0,f1,r1,f3,r3,nex[500005];
void ass(int i)
{
if(i==0)
{
printf("%d\n",f0);
int temp=nex[f0];
if(f3==0)
f3=r3=f0;
else
nex[r3]=f0,r3=f0;
nex[f0]=0;
f0=temp;
}
else if(i==1)
{
if(f3==0||f1&&f1<f3)
{
printf("%d\n",f1);
f1=nex[f1];
}
else if(f1==0||f3&&f3<f1)
{
printf("%d\n",f3);
f3=nex[f3];
}
}
}
int main()
{
int i,j,t,n,m;
char ch;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
getchar();
f0=r0=f1=r1=f3=r3=0;/**< 指针为空 */
memset(nex,0,sizeof(nex));
for(i=1; i<=n; i++)
{
ch=getchar();
if(ch=='0')
{
if(f0==0)
f0=r0=i;
else
nex[r0]=i,r0=i;
}
else if(ch=='1')
{
if(f1==0)
f1=r1=i;
else
nex[r1]=i,r1=i;
}
}
scanf("%d",&m);
getchar();
for(i=1; i<=m; i++)
{
ch=getchar();
if(ch=='M')
{
if(f3||f1)
ass(1);
else
ass(0);
}
else
{
if(f0)
ass(0);
else
ass(1);
}
}
}
return 0;
}
这题卡输入输出，不用br，bw会超时
import java.util.*;
import java.io.*;
public class Main {
static int N = 500010, M = 2 * N;
static int T, n, m;
static char[] seat = new char[N];
static char[] human = new char[M];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
T = Integer.parseInt(br.readLine());
while (T-- > 0) {
n = Integer.parseInt(br.readLine());
seat = br.readLine().toCharArray();
m = Integer.parseInt(br.readLine());
human = br.readLine().toCharArray();
PriorityQueue q0 = new PriorityQueue();
PriorityQueue q1 = new PriorityQueue();
for (int i = 0; i < n; i++) {
if (seat[i] == '0') q0.offer(i + 1);
else if(seat[i] == '1') q1.offer(i + 1);
}
for (int i = 0; i < m; i++) {
if (human[i] == 'M') {
if (!q1.isEmpty()) bw.write(Integer.toString(q1.poll()));
else if (!q0.isEmpty()) {
int t = q0.poll();
q1.offer(t);
bw.write(Integer.toString(t));
}
} else {
if (!q0.isEmpty()) {
int t = q0.poll();
q1.offer(t);
bw.write(Integer.toString(t));
} else if (!q1.isEmpty()) bw.write(Integer.toString(q1.poll()));
}
bw.newLine();
}
}
br.close();
bw.close();
}
}
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个，为啥子
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
