【每日一题Day258】LC2532过桥的时间 | 模拟 优先队列

简介: 【每日一题Day258】LC2532过桥的时间 | 模拟 优先队列

过桥的时间【LC2532】

共有 k 位工人计划将 n 个箱子从旧仓库移动到新仓库。给你两个整数 nk,以及一个二维整数数组 time ,数组的大小为 k x 4 ,其中 time[i] = [leftToRighti, pickOldi, rightToLefti, putNewi]

一条河将两座仓库分隔,只能通过一座桥通行。旧仓库位于河的右岸,新仓库在河的左岸。开始时,所有 k 位工人都在桥的左侧等待。为了移动这些箱子,第 i 位工人(下标从 0 开始)可以:

  • 从左岸(新仓库)跨过桥到右岸(旧仓库),用时 leftToRighti 分钟。
  • 从旧仓库选择一个箱子,并返回到桥边,用时 pickOldi 分钟。不同工人可以同时搬起所选的箱子。
  • 从右岸(旧仓库)跨过桥到左岸(新仓库),用时 rightToLefti 分钟。
  • 将箱子放入新仓库,并返回到桥边,用时 putNewi 分钟。不同工人可以同时放下所选的箱子。

如果满足下面任一条件,则认为工人 i效率低于 工人 j

  • leftToRighti + rightToLefti > leftToRightj + rightToLeftj
  • leftToRighti + rightToLefti == leftToRightj + rightToLeftji > j

工人通过桥时需要遵循以下规则:

  • 如果工人 x 到达桥边时,工人 y 正在过桥,那么工人 x 需要在桥边等待。
  • 如果没有正在过桥的工人,那么在桥右边等待的工人可以先过桥。如果同时有多个工人在右边等待,那么 效率最低 的工人会先过桥
  • 如果没有正在过桥的工人,且桥右边也没有在等待的工人,同时旧仓库还剩下至少一个箱子需要搬运,此时在桥左边的工人可以过桥。如果同时有多个工人在左边等待,那么 效率最低 的工人会先过桥。

所有 n 个盒子都需要放入新仓库,请你返回最后一个搬运箱子的工人 到达河左岸 的时间。

思路:使用四个堆存放工人的下标和完成事件或者到达桥的时间,然后根据要求过桥、搬运箱子,放回最后一个搬运箱子的工人到达河左岸的时间

  • 首先将time数组排序,排序后下标越大,效率越低,优先级越高
  • 使用四个堆存放工人的下标和完成事件或者到达桥的时间

workL新仓库正在放箱的工人【在当前时间之前的所有工人均以完成事件,因此根据时间从小到大排序】

waitL新仓库等待过桥的工人【低效率的先过桥,根据下标从大到小排序】【到达对岸的时间非必须,辅助作用】

workR旧仓库正在拿箱的工人【在当前时间之前的所有工人均以完成事件,因此根据时间从小到大排序】

waitLR旧仓库等待过桥的工人【低效率的先过桥,根据下标从大到小排序】

  • 使用变量cur记录当前的时间,初始时,所有工人位于新仓库,因此将所有节点放入waitL
  • 然后模拟整个流程,计算n个工人从旧仓库到达新仓库,并选择箱子的时间

将workL和workR中所有完成工作的工人,放入排队列表

选择右岸效率最低的工人过桥,若无,再选择左岸效率最低的工人过桥:时间cur移动至其到达对岸的时间节点,并更新其完成工作的时间,最后将其放入工作列表

若两个排队列表均为空,说明工人都在working,那么选择最快完成工作的工人,让他排队过桥

最后,计算所有工人回到左岸的时间,返回最终时间即可

分析可知,此时waitR一定没有元素【因为退出循环的条件是有n个员工到达右岸,如果waitR中有元素的话,n一定不为0,因此最后一个员工到达右岸时,waitR一定没有元素】,而workR一定有元素,其他两个堆是否有元素不影响结果,因此将workR中工作的所有员工依次出队,若当前时间在其完成工作的时间之前,那么需要更新当前时间为其完成工作的时间,然后将当前时间更新为其到达左岸的时间,最后返回cur【堆中根据完成时间从小到大排序,而每次只能过桥一个员工,因此可得最终时间】

实现


         

复杂度

时间复杂度:O ( n + l o g k )

空间复杂度:O ( k )

目录
打赏
0
0
0
0
5
分享
相关文章
|
9月前
|
C++
手把手教你创建一个猜数字游戏!小白专属~
手把手教你创建一个猜数字游戏!小白专属~
282 0
JavaScript练习(统计包含"a"或"A"的字符串个数)
JavaScript练习(统计包含"a"或"A"的字符串个数)
467 0
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
仅用3分钟,百炼调用满血版Deepseek-r1 API,享受百万免费Token。阿里云提供零门槛、快速部署的解决方案,支持云控制台和Cloud Shell两种方式,操作简便。Deepseek-r1满血版在推理能力上表现出色,尤其擅长数学、代码和自然语言处理任务,使用过程中无卡顿,体验丝滑。结合Chatbox工具,用户可轻松掌控模型,提升工作效率。阿里云大模型服务平台百炼不仅速度快,还确保数据安全,值得信赖。
148905 24
深度评测 | 仅用3分钟,百炼调用满血版 Deepseek-r1 API,百万Token免费用,简直不要太爽。
用DeepSeek,就在阿里云!四种方式助您快速使用 DeepSeek-R1 满血版!更有内部实战指导!
DeepSeek自发布以来,凭借卓越的技术性能和开源策略迅速吸引了全球关注。DeepSeek-R1作为系列中的佼佼者,在多个基准测试中超越现有顶尖模型,展现了强大的推理能力。然而,由于其爆火及受到黑客攻击,官网使用受限,影响用户体验。为解决这一问题,阿里云提供了多种解决方案。
16752 37
PAI Model Gallery 支持云上一键部署 DeepSeek-V3、DeepSeek-R1 系列模型
DeepSeek 系列模型以其卓越性能在全球范围内备受瞩目,多次评测中表现优异,性能接近甚至超越国际顶尖闭源模型(如OpenAI的GPT-4、Claude-3.5-Sonnet等)。企业用户和开发者可使用 PAI 平台一键部署 DeepSeek 系列模型,实现 DeepSeek 系列模型与现有业务的高效融合。
本地部署DeepSeek模型
要在本地部署DeepSeek模型,需准备Linux(推荐Ubuntu 20.04+)或兼容的Windows/macOS环境,配备NVIDIA GPU(建议RTX 3060+)。安装Python 3.8+、PyTorch/TensorFlow等依赖,并通过官方渠道下载模型文件。配置模型后,编写推理脚本进行测试,可选使用FastAPI服务化部署或Docker容器化。注意资源监控和许可协议。
1306 8
手把手教你使用 Ollama 和 LobeChat 快速本地部署 DeepSeek R1 模型,创建个性化 AI 助手
DeepSeek R1 + LobeChat + Ollama:快速本地部署模型,创建个性化 AI 助手
3415 117
手把手教你使用 Ollama 和 LobeChat 快速本地部署 DeepSeek R1 模型,创建个性化 AI 助手
DeepSeek全尺寸模型上线阿里云百炼!
阿里云百炼平台近日上线了DeepSeek-V3、DeepSeek-R1及其蒸馏版本等六款全尺寸AI模型,参数量达671B,提供高达100万免费tokens。这些模型在数学、代码、自然语言推理等任务上表现出色,支持灵活调用和经济高效的解决方案,助力开发者和企业加速创新与数字化转型。示例代码展示了如何通过API使用DeepSeek-R1模型进行推理,用户可轻松获取思考过程和最终答案。
如何在通义灵码里用上DeepSeek-V3 和 DeepSeek-R1 满血版671B模型?
除了 AI 程序员的重磅上线外,近期通义灵码能力再升级全新上线模型选择功能,目前已经支持 Qwen2.5、DeepSeek-V3 和 R1系列模型,用户可以在 VSCode 和 JetBrains 里搜索并下载最新通义灵码插件,在输入框里选择模型,即可轻松切换模型。
932 14
阿里云PAI部署DeepSeek及调用
本文介绍如何在阿里云PAI EAS上部署DeepSeek模型,涵盖7B模型的部署、SDK和API调用。7B模型只需一张A10显卡,部署时间约10分钟。文章详细展示了模型信息查看、在线调试及通过OpenAI SDK和Python Requests进行调用的步骤,并附有测试结果和参考文档链接。
1938 9
阿里云PAI部署DeepSeek及调用

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等