公司食堂

使用三个小根堆，分别存储当前人数为0,1,2的三种桌子的桌号，记为pq0,pq1,pq2

以男职员为例：

1. 先尝试坐人数为1的桌子，该桌子人数就变成了2，等价于：将pq1的堆顶弹出，同时推入pq2
2. 如果没有人数为1的桌子了，等价于pq1为空，就去坐人数为0的桌子，等价于：将pq0的堆顶弹出，同时推入pq1

因为桌号存储在优先队列，所以堆顶的桌号总是最小的，保证每个人有多个选择时优先坐最左边的桌子。

女职员同理。

时间复杂度：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 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;
}

#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';
                    }
                }
            }
        }
        
    }
    
    
    
}

o(n) 时间复杂度的屎山golang代码

package main

import (
    "bufio"
    "fmt"
    "os"
)

type g struct {
    a int
    b int
}

func main() {
    r := bufio.NewReader(os.Stdin)
    w := bufio.NewWriter(os.Stdout)
    defer w.Flush()
    var t int
    fmt.Fscan(r, &t)
    for z := 0; z < t; z++ {
        var n, m int
        var bn, bm []byte
        fmt.Fscan(r, &n, &bn, &m, &bm)
        var mi, fi int
        q := make([]int, 1000001)
        var hh, tt int
        nextI := -1
        for ii := 0; ii < len(bm); ii++ {
            v := bm[ii]
            isOk := false
            if v == 'M' {
                if nextI != -1 {
                    if hh != tt && q[hh] < nextI {
                        qi := q[hh]
                        fmt.Fprintln(w, qi+1)
                        hh++
                        isOk = true

                    } else {
                        fmt.Fprintln(w, nextI+1)
                        mi = nextI + 1
                        isOk = true
                        nextI = -1
                    }
                } else {
                    for i := mi; i < n; i++ {
                        if bn[i] == '1' {
                            if hh != tt {
                                qi := q[hh]
                                if qi < i {
                                    fmt.Fprintln(w, qi+1)
                                    hh++
                                    isOk = true

                                    nextI = i
                                    break
                                }
                            }
                            fmt.Fprintln(w, i+1)
                            mi = i + 1
                            isOk = true
                            break
                        }
                    }
                }

                if !isOk {
                    mi = n
                    if hh != tt {
                        qi := q[hh]
                        fmt.Fprintln(w, qi+1)
                        hh++
                        isOk = true

                    } else {
                        bm[ii] = 'F'
                        ii--
                    }

                }
            } else {
                for i := fi; i < n; i++ {
                    if bn[i] == '0' {
                        fmt.Fprintln(w, i+1)
                        q[tt] = i
                        tt++
                        fi = i + 1
                        isOk = true
                        break
                    }
                }
                if !isOk {
                    fi = n
                    bm[ii] = 'M'
                    ii--
                }
            }

        }
    }
}

#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;
}

小记一下
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();
    }
}