最新华为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(max_gems, right - left + 1)

    return max_gems

if __name__ == "__main__":
    n = int(input())
    gems = [int(input()) for _ in range(n)]
    v = int(input())

    print(max_gems(gems, v))

• Java

import java.util.Scanner;

public class Main {
    public static int maxGems(int[] gems, int value) {
        int n = gems.length;
        int left = 0, right = 0, window_sum = 0, max_gems = 0;

        while (right < n) {
            window_sum += gems[right];

            while (window_sum > value) {
                window_sum -= gems[left];
                left++;
            }

            max_gems = Math.max(max_gems, right - left + 1);
            right++;
        }

        return max_gems;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] gems = new int[n];
        for (int i = 0; i < n; i++) {
            gems[i] = scanner.nextInt();
        }
        int v = scanner.nextInt();

        System.out.println(maxGems(gems, v));
    }
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;

int maxGems(vector<int>& gems, int value) {
    int n = gems.size();
    int left = 0, right = 0, window_sum = 0, max_gems = 0;

    while (right < n) {
        window_sum += gems[right];

        while (window_sum > value) {
            window_sum -= gems[left];
            left++;
        }

        max_gems = max(max_gems, right - left + 1);
        right++;
    }

    return max_gems;
}

int main() {
    int n, v;
    cin >> n;
    vector<int> gems(n);
    for (int i = 0; i < n; i++) {
        cin >> gems[i];
    }
    cin >> v;

    cout << maxGems(gems, v) << endl;
    return 0;
}