本题可以直接使用队列模拟。
把大厅中的等待顾客按顺序放入队列,窗口用数组记录当前正在服务的顾客编号。
核心规则如下:
富春包子被誉为扬州包子的“天花板”, 前来购买的顾客络绎不绝。
大厅中有 n 位顾客等待叫号 (按顾客到大厅取号的顺序, 第一个取号的是第 0 位, 以此类推.. (最多 101 位顾客, 且不会有新顾客到来) ) ;
包子铺有 m 个窗口, 每个窗口每次服务一位顾客, 服务时长 1 秒; 当有多个窗口空闲时, 会从大厅队伍中同时叫号, 不会让窗口空闲 (比如大厅有 3 个人, 空着 2 个窗口, 会从大厅中叫前 2 个人分配到空闲窗口) , 且系统会优先分配编号最小的窗口;
每位顾客一次只能买一笼包子, 如果他已买到想要的包子笼数, 会直接离开大厅; 如果还想买更多, 需回到大厅重新取号, 取号后排到等待叫号的顾客末尾。
给你一个整数数组 baskets, 数组长度为 n, baskets[i] 是第 i 位顾客想要购买包子的笼数。请计算出在大厅中排在第 k 位的顾客购买完所有包子时, 其花费的总时间 (秒)。
第一行: 购买包子列表 baskets, 列表中每个元素表示顾客计划购买的包子笼数 (1≤baskets[i]≤100, 顾客数量 n 的约束条件为 0<n≤101) , 以空格隔开
第二行: 在大厅中排在第 k 位的顾客 (下标从 0 开始, 0≤k<n)
第三行: 窗口数量 m (0<m≤10)
大厅中排在第 k 位 (下标从 0 开始) 的顾客完成其想要购买包子所需的总时间 (秒)
输入
2 1 2
2
2
输出
3
说明
为方便理解, C0 (2) 表示首位客户需要买包子 2 笼, 以此类推。大厅中队伍初始为 {C0(2),C1(1),C2(2)},
开始分配:
窗口 1 分配给 C0 (需求: 2 笼)
窗口 2 分配给 C1 (需求: 1 笼)
大厅: {C2(2)}
窗口: 窗口 1:C0(2), 窗口 2:C1(1)
1s 后:
C0 买完一笼, 剩余 1 笼, 回到大厅
C1 完成购买, 离开
窗口 1 分配给 C2(需求:2 笼)
窗口 2 分配给 C0(需求:1 笼)
大厅: {}
窗口: 窗口 1:C2(2), 窗口 2:C0(1)
2s 后:
C2 买完一笼, 剩余 1 笼, 回到大厅
C0 完成购买, 离开
窗口 1 分配给C2(需求:1 笼)
大厅: {}
窗口: 窗口 1:C2(1), 窗口 2: 空
3s 后:
目标顾客 C2 完成购买!
总耗时:3 秒
输入
5 3 3 1 4
2
3
输出
4
说明
为方便理解, C0 (5) 表示首位客户需要买包子 5 笼, 以此类推。大厅中队伍初始为 {C0(5),C1(3),C2(3),C3(1),C4(4)}
开始分配:
窗口 1 分配给 C0(需求:5 笼)
窗口 2 分配给 C1(需求:3 笼)
窗口 3 分配给 C2(需求:3 笼)
大厅: {C3(1),C4(4)}
窗口: 窗口 1:C0(5), 窗口 2:C1(3), 窗口 3:C2(3)
1s 后:
C0 买完一笼, 剩余 4 笼, 回到大厅
C1 买完一笼, 剩余 2 笼, 回到大厅
C2 买完一笼, 剩余 2 笼, 回到大厅
窗口 1 分配给 C3(需求:1 笼)
窗口 2 分配给 C4(需求:4 笼)
窗口 3 分配给 C0(需求:4 笼)
大厅: {C1(2),C2(2)}
窗口: 窗口 1:C3(1), 窗口 2:C4(4), 窗口 3:C0(4)
2s 后:
C3 完成购买, 离开
C4 买完一笼, 剩余 3 笼, 回到大厅
C0 买完一笼, 剩余 3 笼, 回到大厅
窗口 1 分配给 C1(需求:2 笼)
窗口 2 分配给 C2(需求:2 笼)
窗口 3 分配给 C4(需求:3 笼)
大厅: {C0(3)}
窗口: 窗口 1:C1(2), 窗口 2:C2(2), 窗口 3:C4(3)
3s 后:
C1 买完一笼, 剩余 1 笼, 回到大厅
C2 买完一笼, 剩余 1 笼, 回到大厅
C4 买完一笼, 剩余 2 笼, 回到大厅
窗口 1 分配给 C0(需求:3 笼)
窗口 2 分配给 C1(需求:1 笼)
窗口 3 分配给 C2(需求:1 笼)
大厅: {C4(2)}
窗口: 窗口 1:C0(3), 窗口 2:C1(1), 窗口 3:C2(1)
4s 后:
C0 买完一笼, 剩余 2 笼, 回到大厅
C1 完成购买, 离开
目标顾客 C2 完成购买!
总耗时:4 秒
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册