最大通关数

2023-12-23 19:08:53

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

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

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

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

等风来，不如追风去……
洛洛和晶晶一起挑战峡谷深渊
最大过关数
(用给定的紫水晶依次通过两个入口的关卡)

本文质量分：

【 96 】

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

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

目?录

  • ◆?最大过关数
    • 1、题目描述
    • 2、算法解析
      • 2.1 过关关卡选择
      • 2. 退出循环选关过关条件设定
      • 2. 次级灰色标题
    • 3、完整源码(Python)


◆?最大过关数


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-8


def 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:
            break

        print(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篇。

    文章来源:https://blog.csdn.net/m0_57158496/article/details/135090916
    本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。