首页 > 试题广场 >

公司食堂

[编程题]公司食堂

热度指数：24056 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

进阶：时间复杂度 $O(nlogn)\$ ,空间复杂度 $O(n)\$

输入描述:

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

输出

算法知识视频讲解

Python

牛客321627531号

Python

import sys
import bisect
from collections import deque
data = sys.stdin.read().splitlines()
T = int(data[0])
ind = 0
ans = []
for _ in range(T):
    N = int(data[ind+1])
    arr = list(map(int,data[ind+2]))
    M = int(data[ind+3])
    num = list(data[ind+4])
    queue_0 = deque()
    queue_1 = deque()
    for idx,val in enumerate(arr):
        if val == 0:
            queue_0.append(idx+1)
        elif val == 1:
            queue_1.append(idx+1)
    for i in range(M):
        if num[i] == 'M':
            if queue_1:
                ans.append(queue_1.popleft())
            else:
                q = queue_0.popleft()
                ans.append(q)
                bisect.insort(queue_1,q)
                # queue_1.append(q)
                # queue_1_list = sorted(queue_1)
                # queue_1 = deque(queue_1_list)
        else:
            if queue_0:
                q = queue_0.popleft()
                ans.append(q)
                bisect.insort(queue_1,q)
                # queue_1.append(q)
                # queue_1_list = sorted(queue_1)
                # queue_1 = deque(queue_1_list)
            else:
                ans.append(queue_1.popleft())
    ind += 4
print('\n'.join(map(str,ans)))

发表于 2025-05-16 23:59:08 回复(0)

Python

ito_

python print爆了有什么方法解决嘛

发表于 2022-03-26 18:34:08 回复(0)

Python

王庭琛

暴力解超时，为啥题解里的那个暴力解能过....

loop = int(input())
while loop:

    desknum = int(input())
    desk = [int(i) for i in input()]
    person = int(input())
    gender = input()
    for i in gender:
        if i == 'M':
            re = -1

            for k in range(len(desk)):
                if desk[k] ==1:
                    re = k
                    break

            if re != -1:
                desk[re] += 1
            else:
                for k in range(len(desk)):
                    if desk[k] == 0:
                        re = k
                        break
                desk[re] += 1
            print(re + 1)
        else:
            re = -1
            for k in range(len(desk)):
                if desk[k] == 0:
                    re = k
                    break
            if re != -1:
                desk[re] += 1
            else:
                for k in range(len(desk)):
                    if desk[k] == 1:
                        re = k
                        break

                desk[re] += 1
            print(re + 1,)
    loop -= 1

发表于 2021-05-11 01:15:53 回复(0)

Python

华为26届校园招聘官

超时怎么办----------啊啊啊啊，发现这上面刷题不如某code

bb = int(input())
for _ in range(bb):
    desk_nums = int(input())
    one_desk = input()
    xx = int(input())
    people_class = input()
    for item in range(xx):
        if people_class[item] == 'M':
            ind = one_desk.find('1')
            if ind != -1:
                print(ind+1)
                one_desk = one_desk.replace('1', '2',1)
            else:
                print(one_desk.find('0')+1)
                one_desk = one_desk.replace('0', '1',1)
        else:
            ind = one_desk.find('0')
            if ind != -1:
                print(ind+1)
                one_desk = one_desk.replace('0', '1',1)
            else:
                print(one_desk.find('1')+1)
                one_desk = one_desk.replace('1', '2',1)

发表于 2021-03-14 16:05:28 回复(0)