(C卷,100分)- 最多购买宝石数目（Java & JS & Python & C）

题目描述

橱窗里有一排宝石，不同的宝石对应不同的价格，宝石的价格标记为 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为例：蓝色为L指针，橙色为R指针

以上就是双指针的运行逻辑。

其中需要注意的是，如果内部和超过了v，那么此时我们需要不停右移L指针，来减少内部和，直到内部和<=v时，结束L指针右移。然后才能开始R指针右移。

还有一种特殊情况比如：

gems = [1,2,3,100,4,5,6]，v = 10

更多实现细节，请结合代码注释理解。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // 橱窗中宝石的总数量
  const n = parseInt(await readline());

  // n个宝石的价格
  const gems = [];
  for (let i = 0; i < n; i++) {
    gems[i] = parseInt(await readline());
  }

  // 你拥有的钱
  const v = parseInt(await readline());

  // 记录题解
  let ans = 0;

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

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

  outer: 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);

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

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

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

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

  console.log(ans);
})();

Java算法源码

import java.util.Scanner;

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

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

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

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

    // 记录题解
    int ans = 0;

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

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

    outer:
    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);

        while (l < r) {
          // 由于纳入r位置宝石后，总和超过了拥有的钱，因此我们尝试丢弃l指针宝石，即l++
          window_sum -= gems[l++];
          if (window_sum <= v) {
            // 如果丢弃l宝石后，总和不超过拥有的钱，则继续纳入r后面的宝石
            r++;
            continue outer;
          }
        }

        // 如果把 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);
  }
}

Python算法源码

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

gems = []  # n个宝石的价格
for _ in range(n):
    gems.append(int(input()))

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


# 算法入口
def getResult():
    # 记录题解
    ans = 0

    # 双指针
    l = 0
    r = 0

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

    while r < n:
        # 加入r指针指向的元素
        window_sum += gems[r]

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

            flag = False

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

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

            if flag:
                continue

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

    # 收尾操作
    if window_sum <= v:
        ans = max(ans, r - l)

    return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int main() {
    // 橱窗中宝石的总数量
    int n;
    scanf("%d", &n);

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

    // 你拥有的钱
    int v;
    scanf("%d", &v);

    // 记录题解
    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 = 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) {
                continue;
            }

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

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

    printf("%dn", ans);

    return 0;
}