返回目录

最多购买宝石数目

知识点数组前缀和

时间限制：3s 空间限制：256MB 限定语言：不限

题目描述：

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

宝石可同时出售0个或多个，如果同时出售多个，则要求出售的宝石编号连续；例如客户最大购买宝石个数为m，购买的宝石编号必须为gems[i],gems[i+1]...gems[i+m+1]
假设你当前拥有总面值为value的钱，请问最多能购买到多少个宝石,如无法购买宝石，则返回0.

输入描述：

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

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

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

输出描述：

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

Python算法源码

class GemShop:
    def __init__(self, gems, budget):
        self.gems = gems  # 宝石价格列表
        self.budget = budget  # 拥有的钱

    def purchase_gems(self):
        """
        在给定预算内购买宝石的最大数量
        """
        total_gems = len(self.gems)  # 橱窗中宝石的总数量

        # 记录最大购买数量
        max_purchased = 0

        # 双指针
        left = 0
        right = 0

        # 双指针范围内的和
        window_sum = 0

        while right < total_gems:
            # 加入right指针指向的元素
            window_sum += self.gems[right]

            if window_sum <= self.budget:
                # 如果总和不超过拥有的钱，则继续加入后面的
                right += 1
            else:
                # 如果总和超过了拥有的钱，则 [left, right-1] 范围的宝石是能够买下的，记录此时的宝石数量 right-1 - left + 1
                max_purchased = max(max_purchased, right - left)

                flag = False

                while left < right:
                    # 由于纳入right位置宝石后，总和超过了拥有的钱，因此我们尝试丢弃left指针宝石，即left++
                    window_sum -= self.gems[left]
                    left += 1

                    if window_sum <= self.budget:
                        # 如果丢弃left宝石后，总和不超过拥有的钱，则继续纳入right后面的宝石
                        right += 1
                        flag = True
                        break

                if flag:
                    continue

                # 如果把 left ~ right - 1 范围宝石都丢弃了，总和任然超过拥有的钱，那么就right宝石的价值就超过了手中的钱，此时双指针范围内不能包含right位置
                # 此时可以将left,right全部移动到right+1位置
                right += 1
                left = right
                window_sum = 0

        # 收尾操作
        if window_sum <= self.budget:
            max_purchased = max(max_purchased, right - left)

        return max_purchased


# 输入获取
total_gems = int(input())  # 橱窗中宝石的总数量

gem_prices = []  # 宝石价格列表
for _ in range(total_gems):
    gem_prices.append(int(input()))

budget_amount = int(input())  # 你拥有的钱

# 创建宝石商店实例
gem_shop = GemShop(gem_prices, budget_amount)

# 获取结果并输出
print(gem_shop.purchase_gems())

C算法源码

#include <stdio.h>

int gems[100000]; // 假设最大数组大小
int n;            // 宝石的数量
int v;            // 可用的钱

// 计算结果的函数
int getResult() {
    // 用于存储结果的变量
    int ans = 0;

    // 两个指针
    int l = 0;
    int r = 0;

    // 窗口中元素的总和
    int window_sum = 0;

    while (r < n) {
        // 将指向的元素加入窗口总和
        window_sum += gems[r];

        if (window_sum <= v) {
            // 如果总和在预算范围内，则将右指针向前移动
            r++;
        } else {
            // 如果总和超出预算，则计算当前窗口中可以购买的宝石数量
            ans = ans > (r - l) ? ans : (r - l);

            // 尝试通过将左指针向前移动来减少窗口总和
            int flag = 0;
            while (l < r) {
                window_sum -= gems[l];
                l++;

                if (window_sum <= v) {
                    // 如果减少窗口总和使其在预算范围内，则跳出循环并将右指针向前移动
                    r++;
                    flag = 1;
                    break;
                }
            }

            if (flag) {
                continue;
            }

            // 如果当前窗口中的所有宝石都被丢弃，但总和仍超出预算，
            // 则将两个指针都移动到下一个位置
            r++;
            l = r;
            window_sum = 0;
        }
    }

    // 最后的检查
    if (window_sum <= v) {
        ans = ans > (r - l) ? ans : (r - l);
    }

    return ans;
}

int main() {
    // 输入：宝石的数量
    scanf("%d", &n);

    // 输入：每个宝石的价格
    for (int i = 0; i < n; i++) {
        scanf("%d", &gems[i]);
    }

    // 输入：可用的钱
    scanf("%d", &v);

    // 输出：算法的结果
    printf("%d\n", getResult());

    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 橱窗中宝石的总数量
        int n = scanner.nextInt();

        // n个宝石的价格
        int[] gems = new int[n];
        for (int i = 0; i < n; i++) {
            gems[i] = scanner.nextInt();
        }

        // 你拥有的钱
        int v = scanner.nextInt();

        // 记录题解
        int ans = 0;

        // 双指针
        int l = 0;
        int r = 0;

        // 双指针范围内的和
        int window_sum = 0;

        while (r < n) {
            // 加入r指针指向的元素
            window_sum += gems[r];

            if (window_sum <= v) {
                // 如果总和不超过拥有的钱，则继续加入后面的
                r++;
            } else {
                // 如果总和超过了拥有的钱，则 [l, r-1] 范围的宝石是能够买下的，记录此时的宝石数量 r-1 - l + 1
                ans = Math.max(ans, r - l);

                int flag = 0;

                while (l < r) {
                    // 由于纳入r位置宝石后，总和超过了拥有的钱，因此我们尝试丢弃l指针宝石，即l++
                    window_sum -= gems[l++];

                    if (window_sum <= v) {
                        // 如果丢弃l宝石后，总和不超过拥有的钱，则继续纳入r后面的宝石
                        r++;
                        flag = 1;
                        break;
                    }
                }

                if (flag == 1) {
                    continue;
                }

                // 如果把 l ~ r - 1 范围宝石都丢弃了，总和任然超过拥有的钱，那么就r宝石的价值就超过了手中的钱，此时双指针范围内不能包含r位置
                // 此时可以将l,r全部移动到r+1位置
                l = ++r;
                window_sum = 0;
            }
        }

        // 收尾操作
        if (window_sum <= v) {
            ans = Math.max(ans, r - l);
        }

        System.out.println(ans);
    }
}