首页 > 试题广场 >

公司食堂

[编程题]公司食堂
  • 热度指数：23690 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

小美和小团所在公司的食堂有N张餐桌，从左到右摆成一排，每张餐桌有2张餐椅供至多2人用餐，公司职员排队进入食堂用餐。小美发现职员用餐的一个规律并告诉小团：当男职员进入食堂时，他会优先选择已经坐有1人的餐桌用餐，只有当每张餐桌要么空着要么坐满2人时，他才会考虑空着的餐桌；

当女职员进入食堂时，她会优先选择未坐人的餐桌用餐，只有当每张餐桌都坐有至少1人时，她才会考虑已经坐有1人的餐桌；

无论男女，当有多张餐桌供职员选择时，他会选择最靠左的餐桌用餐。现在食堂内已有若干人在用餐，另外M个人正排队进入食堂，小团会根据小美告诉他的规律预测排队的每个人分别会坐哪张餐桌。

进阶：时间复杂度,空间复杂度

输入描述:
第一行输入一个整数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

输入

1
5
01102
6
MFMMFF

输出

2
1
1
3
4
4
算法知识视频讲解
开通博客
头像 ChenJianhui
发表于 2021-03-14 15:48:46
美团笔试题——公司食堂原理：小根堆，利用优先队列实现。设置seat0和seat1两个优先队列，存放位置为0和1的餐桌号，因小根堆特性，队首为最小值，即较左端餐桌位置。本题卡endl，改为'\n'换行符输出即AC。endl会刷新输出流缓冲区，多行输出会导致刷新缓冲区过于频繁，导致超时问题。 #incl 展开全文
去ta的博客 赞 (14) 回复(0) 收起
头像 大厂算法岗必拿下
发表于 2021-09-22 07:27:11
注意抓住共同的规律。 两个小根堆。 \n可以确保程序通过 #include<bits/stdc++.h> using namespace std; //采用大根堆，小根堆的思想 int main(){ int T,N,M; cin>>T; stri 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 星辰薄荷
发表于 2021-12-13 17:06:53
一开始用的两个小根堆存人数为0和1的座位，后来想想用三个LinkedList就可以了，一个存放一开始人数为0的座位，一个存放一开始人数为1的座位，还有一个存放人数由0变为1的座位，需要查找人数为1的座位时，比较后两个List的首元素大小，如果其中一个为空，就选择另外一个。 其实这题考的是IO的处理吧 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 bytedancers
发表于 2021-03-12 02:33:16
T = int(input().strip()) import heapq def find_next(tables, i, num): tlen = len(tables) while i < tlen and tables[i] != num: i += 1 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 谦虚的布莱恩在线蹲牛友
发表于 2023-02-04 09:56:29
小记一下 List+ TreeSet超时 List+ PriorityQueue 超时 数组模拟+双指针 超时 最后发现是卡的输入输出 坑点：writer.flush 最后一次刷新输出写一次刷新一次只能过11个点 数组模拟+双指针 o(n) 版本如下 import java.util.Arrays; 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 chen06
发表于 2021-03-12 22:00:49
GO版本优先队列实现 package main import ( "container/heap" "fmt" ) type IntHeap []int func (h IntHeap) Len() int { return len(h) } func (h 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 小牛冲冲冲jiang
发表于 2021-09-22 06:27:52
双指针最后一个无法通过 卡输出 StringBuilder sb = new StringBuilder();sb.append(输出的字符串)System.out.print(sb);要比println 输出效率高太多 import java.io.*; import java.util.Sca 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 dunaifen
发表于 2022-03-04 09:57:50
一开始用的两个堆，做的时候11的用例一直超时，改成一个，还是超时，最后用三个数组实现，还是超时，破防提交后发现是cin，cout问题。发现题解基本都用堆，提供一个用数组的思路，三个数组p1,p2,p3,p1存储0人桌子，p2储存一开始的1人桌，p3储存由0人桌变成1人桌的1人桌，用三个指针记录三种桌 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 牛客216942348号
发表于 2021-09-03 10:51:22
感觉我会错了题意。。答案是对的，但是就是没办法通过 import java.io.BufferedWriter;import java.io.IOException;import java.io.OutputStreamWriter;import java.util.*; public class 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 我讨厌递归算法
发表于 2023-03-12 15:19:36
和其他的解题稍有不同， 空桌位无需使用小顶堆，只需维护一个list即可，每次poll第一个即可 import java.util.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 iOS工程师 安卓工程师 美团 前端工程师 算法工程师 2021 大数据开发工程师 Java工程师
上传者：小小
难度：
72条回答 21852浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号