最大通关数

洛洛和晶晶计划一起挑战峡谷深渊，峡谷左右有不同数量的关卡，每个关卡需要不同的紫水晶通关，用给定的紫水晶依次通过最多的关卡。

---

(笔记模板由python脚本于2023年12月23日 12:16:50创建，本篇笔记适合熟悉贪心算法的coder翻阅)

---

【学习的细节是欢悦的历程】

---

• Python 官网：https://www.python.org/

• Free：大咖免费“圣经”教程《 python 完全自学教程》，不仅仅是基础那么简单……
  地址：https://lqpybook.readthedocs.io/

---

  自学并不是什么神秘的东西，一个人一辈子自学的时间总是比在学校学习的时间长，没有老师的时候总是比有老师的时候多。
            —— 华罗庚

---

• My CSDN主页、My HOT博、My Python 学习个人备忘录
• 好文力荐、 老齐教室

---

---

洛洛和晶晶一起挑战峡谷深渊 最大过关数 (用给定的紫水晶依次通过两个入口的关卡)

---

---

本文质量分：

【 96 】
本文地址： https://blog.csdn.net/m0_57158496/article/details/135090916

CSDN质量分查询入口：http://www.csdn.net/qc

---

目 录

---

◆ 最大过关数

1、题目描述

• 题目描述截屏图片
  

【 题目来源于 CSDN 问答社区提问“最大通过数”】

---

回页目录

---

2、算法解析

  本题目算法逻辑不难：典型的“贪心算法”。判定比较左右当前关卡所需紫水晶数量，选择较小的过关；如果一样则任意左右。过关后关卡向前推进一关，直到消耗到紫水晶数量都小于当前关卡_{(左右关卡)}所需。左右关卡的遍历，用“双指针”_{(设置left、right两个变量)}很好实现。

  难点在于当左或右关卡一边关卡先过完的情况，这可以引入“无穷大”_{(Python中的无穷大∞是inf字符串，它是浮点型float，其使用形式为用float函数转换字符串“inf”为浮点型：float(‘inf’))}的概念来解决。

• 示例输入效果截屏图片
  
  
  

2.1 过关关卡选择

  判定比较左右当前关卡所需紫水晶数量，选择紫水晶消耗较少的过关；如果所耗紫水晶一样多，则先任意左右，再判定可否再另一边。

Python代码

if left == right: # 先任意左右。if left <= k and ai < n:count += 1 # 已过关卡数累加。k -= left # 更新紫水晶数量。ai += 1 # 左前进一关。if right <= k and bi < m: # 如果紫水晶能通关另一边，就过关。count += 1 # 已过关卡数累加。k -= left # 更新紫水晶数量。bi += 1 # 右前进一关。else:if left < right and k >= left and ai < n:count += 1 # 已过关卡数累加。k -= left # 更新紫水晶数量。ai += 1 # 左前进一关。elif k >= right and bi < m:count += 1 # 已过关卡数累加。k -= right # 更新紫水晶数量。bi += 1 # 右前进一关。

---

回页目录

---

2. 退出循环选关过关条件设定

  当所余紫水晶都不够通关左右关卡，退出选关循环。

• 代码运行效果截屏图片

Python代码

if k <= left and k <= right:break # 当所余紫水晶都不够通关左右关卡，退出选关循环。

---

回页目录

---

2. 次级灰色标题

  描述

• 代码运行效果截屏图片

Python代码

python代码

#!/sur/bin/nve python
# coding: utf-8def max_passages(n, m, k, a, b):count = ai = bi = 0 # 变量初始值。blank = f"{'':>8}"print(f"\n{' 最大过关数 ':=^35}\n\n\n{f'【初始状态】':.^34}\n\n{blank}Left关卡数{n}: {str(a)[1:-1]}\n{blank}Right关卡数{m}: {str(b)[1:-1]}\n{blank}紫水晶: {k}\n{'':.^40}\n\n已过关卡：")while k >= 0:if ai < n:left = a[ai]else:left = float('inf') # 左关卡过完，设置左关卡当前需紫水晶数量为无穷大。if bi < m:right = b[bi]else:right = float('inf') # 右关卡过完，设置右关卡当前需紫水晶数量为无穷大。if k <= left and k <= right:breakprint(f"【第{count+1:>02}关】Left: {left if left != float('inf') else '∞'}, Right: {right if right != float('inf') else '∞'}, 紫水晶: {k}")if left == right:if left <= k and ai < n:count += 1 # 已过关卡数累加。k -= left # 更新紫水晶数量。ai += 1 # 左前进一关。if right <= k and bi < m:count += 1 # 已过关卡数累加。k -= left # 更新紫水晶数量。bi += 1 # 右前进一关。else:if left < right and k >= left and ai < n:count += 1 # 已过关卡数累加。k -= left # 更新紫水晶数量。ai += 1 # 左前进一关。elif k >= right and bi < m:count += 1 # 已过关卡数累加。k -= right # 更新紫水晶数量。bi += 1 # 右前进一关。print(f"\n{'':.^40}\n【第{count+1:>02}关状态】Left: {a[ai] if left != float('inf') else '∞'}, Right: {b[bi] if right != float('inf') else '∞'}, 紫水晶: {k}")return count# 示例
if __name__ == '__main__':n = 5  # 左边入口的关卡数。m = 4  # 右边入口的关卡数。k = 10  # 总共携带的紫水晶数量。a = [1, 2, 3, 4, 5]  # 左边入口每个关卡需要的紫水晶数量。b = [1, 2, 3, 4]  # 右边入口每个关卡需要的紫水晶数量。print(f"\n\n{f' 最大过关数：{max_passages(n, m, k, a, b)} ':=^35}\n\n") # 样例一。print(f"\n\n{f' 最大过关数：{max_passages(2, 2, 10, (1, 2), [3, 5])} ':=^35}\n\n") # 样例二。

---

回页目录

---

3、完整源码(Python)

(源码较长，点此跳过源码)

---

回页首

---

上一篇：  身份证编码校验_{(一道校验居民身份证编码校验码的小题，触发了我对我国第二代身份证整串编码的探究：校验成功，解读编码信息)}
下一篇： 

---

我的HOT博：

  本次共计收集289篇博文笔记信息，总阅读量44.72w。数据采集于2023年12月11日 23:07:13，用时5分11.8秒。阅读量不小于4.0k的有17篇。

• ChatGPT国内镜像站初体验：聊天、Python代码生成等
  地址：https://blog.csdn.net/m0_57158496/article/details/129035387
  浏览阅读：6.2w
  点赞：127 收藏：809 评论：71
  (本篇笔记于2023-02-14 23:46:33首次发布，最后修改于2023-07-03 05:50:55)
   
• 让QQ群昵称色变的神奇代码
  地址：https://blog.csdn.net/m0_57158496/article/details/122566500
  浏览阅读：5.8w
  点赞：24 收藏：86 评论：17
  (本篇笔记于2022-01-18 19:15:08首次发布，最后修改于2022-01-20 07:56:47)
   
• Python列表(list)反序(降序)的7种实现方式
  地址：https://blog.csdn.net/m0_57158496/article/details/128271700
  浏览阅读：9.9k
  点赞：5 收藏：30 评论：8
  (本篇笔记于2022-12-11 23:54:15首次发布，最后修改于2023-03-20 18:13:55)
   
• pandas 数据类型之 DataFrame
  地址：https://blog.csdn.net/m0_57158496/article/details/124525814
  浏览阅读：9.4k
  点赞：7 收藏：34 
  摘要：pandas 数据类型之 DataFrame_panda dataframe。
  (本篇笔记于2022-05-01 13:20:17首次发布，最后修改于2022-05-08 08:46:13)
   
• 个人信息提取(字符串)
  地址：https://blog.csdn.net/m0_57158496/article/details/124244618
  浏览阅读：7.7k
  摘要：个人信息提取(字符串)_python个人信息提取。
  (本篇笔记于2022-04-18 11:07:12首次发布，最后修改于2022-04-20 13:17:54)
   
• Python字符串居中显示
  地址：https://blog.csdn.net/m0_57158496/article/details/122163023
  浏览阅读：7.2k
  评论：1
   
• 罗马数字转换器|罗马数字生成器
  地址：https://blog.csdn.net/m0_57158496/article/details/122592047
  浏览阅读：7.2k
  (本篇笔记于2022-01-19 23:26:42首次发布，最后修改于2022-01-21 18:37:46)
   
• 斐波那契数列的递归实现和for实现
  地址：https://blog.csdn.net/m0_57158496/article/details/122355295
  浏览阅读：5.6k
  点赞：4 收藏：2 评论：8
   
• 回车符、换行符和回车换行符
  地址：https://blog.csdn.net/m0_57158496/article/details/123109488
  浏览阅读：5.5k
  点赞：2 收藏：3 
  摘要：回车符、换行符和回车换行符_命令行回车符。
  (本篇笔记于2022-02-24 13:10:02首次发布，最后修改于2022-02-25 20:07:40)
   
• python清屏
  地址：https://blog.csdn.net/m0_57158496/article/details/120762101
  浏览阅读：5.3k
   
• 练习：字符串统计(坑：f‘string‘报错)
  地址：https://blog.csdn.net/m0_57158496/article/details/121723096
  浏览阅读：5.1k
   
• 练习：尼姆游戏(聪明版/傻瓜式•人机对战)
  地址：https://blog.csdn.net/m0_57158496/article/details/121645399
  浏览阅读：5.1k
  点赞：14 收藏：44 
   
• 我的 Python.color() (Python 色彩打印控制)
  地址：https://blog.csdn.net/m0_57158496/article/details/123194259
  浏览阅读：4.6k
  点赞：2 收藏：8 
  摘要：我的 Python.color() (Python 色彩打印控制)_python color。
  (本篇笔记于2022-02-28 22:46:21首次发布，最后修改于2022-03-03 10:30:03)
   
• 练习：生成100个随机正整数
  地址：https://blog.csdn.net/m0_57158496/article/details/122558220
  浏览阅读：4.6k
  (本篇笔记于2022-01-18 13:31:36首次发布，最后修改于2022-01-20 07:58:12)
   
• 密码强度检测器
  地址：https://blog.csdn.net/m0_57158496/article/details/121739694
  浏览阅读：4.4k
  (本篇笔记于2021-12-06 09:08:25首次发布，最后修改于2022-11-27 09:39:39)
   
• 罗马数字转换器(用罗马数字构造元素的值取模实现)
  地址：https://blog.csdn.net/m0_57158496/article/details/122608526
  浏览阅读：4.2k
  (本篇笔记于2022-01-20 19:38:12首次发布，最后修改于2022-01-21 18:32:02)
   
• 练习：班里有人和我同生日难吗？(概率probability、蒙特卡洛随机模拟法)
  地址：https://blog.csdn.net/m0_57158496/article/details/124424935
  浏览阅读：4.0k
  摘要：班里有人和我同生日难吗？(概率probability、蒙特卡洛随机模拟法)_生日模拟问题,计算频率,并画出随着试验次数n的增大,频率和理论概率的 关系图。
  (本篇笔记于2022-04-26 12:46:25首次发布，最后修改于2022-04-27 21:22:07)
   

• ---

  推荐条件 阅读量突破4.0k (更多热博，请点击蓝色文字跳转翻阅)

  
  

  ---

  回页首

  ---

  
  
  

  精品文章：

  • 好文力荐：齐伟书稿 《python 完全自学教程》 Free连载(已完稿并集结成书，还有PDF版本百度网盘永久分享，点击跳转免费🆓下载。)
  • OPP三大特性：封装中的property
  • 通过内置对象理解python'
  • 正则表达式
  • python中“*”的作用
  • Python 完全自学手册
  • 海象运算符
  • Python中的 `!=`与`is not`不同
  • 学习编程的正确方法

  来源：老齐教室

  ---

  ◆ Python 入门指南【Python 3.6.3】

  ---

  好文力荐：

  • 全栈领域优质创作者——[寒佬]_{(还是国内某高校学生)}博文“非技术文—关于英语和如何正确的提问”，“英语”和“会提问”是编程学习的两大利器。
  • 【8大编程语言的适用领域】先别着急选语言学编程，先看它们能干嘛
  • 靠谱程序员的好习惯
  • 大佬帅地的优质好文“函数功能、结束条件、函数等价式”三大要素让您认清递归

  ---

  CSDN实用技巧博文：

  • 8个好用到爆的Python实用技巧
  • python忽略警告
  • Python代码编写规范
  • Python的docstring规范（说明文档的规范写法）

  ---