最大通关数

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
    本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。