最新华为OD机试真题-宝石购买计划(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=> 宝石购买计划(100分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🍊 宝石购买计划

题目描述

K小姐经营着一家珠宝店,店里的橱窗中陈列着一排 颗宝石。每颗宝石都有各自的价格,第 颗宝石的价格为 。宝石可以同时出售 个或多个,但如果要同时出售多颗宝石,则这些宝石在橱窗中的位置必须连续。例如,如果顾客最多购买 颗宝石,那么他可以选择购买的宝石编号为 。

现在,K小姐手中有 元钱,她想知道自己最多能购买到多少颗宝石。如果没有足够的钱购买任何宝石,则返回 。

输入格式

第一行包含一个正整数 ,表示橱窗中宝石的总数量。

接下来的 行,每行包含一个正整数,分别表示从第 颗宝石到第 颗宝石的价格,即 到 。

最后一行包含一个正整数 ,表示K小姐手中的钱数。

输出格式

输出一个整数,表示K小姐最多能购买到的宝石数量。

样例输入

7
8
4
6
3
1
6
7
10

样例输出

3

样例解释

最多可以购买的宝石为 至 或者 至 。

数据范围

题解

本题可以使用双指针滑动窗口的思想来解决。我们用两个指针 和 分别表示当前窗口的左右边界,窗口内的宝石就是当前选择购买的宝石。我们维护窗口内宝石价格的总和 ,初始时 。

我们不断向右移动 指针,将宝石价格累加到 中,直到 超过预算 。此时,我们可以确定 范围内的宝石是可以购买的,更新答案为 。

接下来,我们需要缩小窗口的大小,即向右移动 指针,并从 中减去相应的宝石价格,直到 不超过预算 。然后继续向右移动 指针,重复上述过程。

如果在移动 指针的过程中,将 范围内的宝石都移除后 仍然超过预算 ,那么说明 指针指向的宝石价格太高,我们无法购买,此时可以直接将 和 都移动到 的位置,重新开始寻找。

最后,当 指针移动到数组末尾时,我们还需要再次判断 是否不超过预算 ,如果是,则更新答案。

时间复杂度为 ,空间复杂度为 。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()
def max_gems(gems, value):
    left = 0
    window_sum = 0
    max_gems = 0

    for right in range(len(gems)):
        window_sum += gems[right]

        while window_sum > value:
            window_sum -= gems[left]
            left += 1

        max_gems = max(m