最新华为OD机试真题-宝石购买计划(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓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
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-E/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 部分题目提供OJ在线评测