橱窗宝石 - 华为OD统一考试

OD统一考试（C卷）

分值： 100分

题解： Java / Python / C++

alt

题目描述

橱窗里有一排宝石，不同的宝石对应不同的价格，宝石的价格标记为 gems[i],0<=i<n, n = gems.length

宝石可同时出售0个或多个，如果同时出售多个，则要求出售的宝石编号连续；

例如客户最大购买宝石个数为m，购买的宝石编号必须为gems[i],gems[i+1]…gems[i+m-1](0<=i<n,m<=n)

假设你当前拥有总面值为value的钱，请问最多能购买到多少个宝石,如无法购买宝石，则返回 0。

输入描述

第一行输入n，参数类型为int，取值范围：[0,10^6]，表示橱窗中宝石的总数量。

之后n行分别表示从第0个到第n-1个宝石的价格，即gems[0]到gems[n-1]的价格，类型为int，取值范围：(0,1000]。

之后一行输入v，类型为int，取值范围：[0,10^9]表示你拥有的钱。

输出描述

输出int类型的返回值，表示最大可购买的宝石数量。

示例1

输入：
7
8
4
6
3
1
6
7
10

输出：
3

示例2

输入：
0
1

输出：
0

说明：
因为没有宝石，所以返回 0

示例3

题解

滑动窗口的方法来解决。具体步骤如下：

初始化滑动窗口的左边界和右边界为0。
遍历右边界，累加宝石的价格，直到总价格大于等于拥有的钱或者遍历完所有宝石。
如果总价格小于等于拥有的钱，更新最大购买宝石数量。
移动左边界，减去左边界对应的宝石价格，直到总价格小于拥有的钱。
重复步骤2到步骤4，直到右边界遍历完所有宝石。

Java

java">import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {
    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();

        // 使用滑动窗口求解
        int left = 0, right = 0, total = 0, maxCount = 0;

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

            // 收缩左边界
            while (total > v) {
                total -= gems[left];
                left++;
            }

            // 更新最大购买宝石数量
            maxCount = Math.max(maxCount, right - left + 1);

            right++;
        }

        System.out.println(maxCount);
    }
}

Python

python">n = int(input())
gems = [int(input()) for _ in range(n)]
v = int(input())

left, total, maxCount = 0, 0, 0
for right in range(n):
    total += gems[right]

    while total > v:
        total -= gems[left]
        left += 1
    
    maxCount = max(maxCount, right - left + 1)

print(maxCount)

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;

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

    int v;
    cin >> v;

    int left = 0, right = 0, total = 0, maxCount = 0;
    while (right < n) {
        total += gems[right];

        // 收缩左边界
        while (total > v) {
            total -= gems[left];
            left++;
        }

        // 更新最大购买宝石数量
        maxCount = max(maxCount, right - left + 1);

        right++;
    }

    cout << maxCount << endl;

    return 0;
}