(B卷,100分)- 最大花费金额（Java & JS & Python & C）

题目描述

双十一众多商品进行打折销售，小明想购买自己心仪的一些物品，但由于受购买资金限制，所以他决定从众多心仪商品中购买三件，而且想尽可能的花完资金。

现在请你设计一个程序帮助小明计算尽可能花费的最大资金数额。

输入描述

• 输入第一行为一维整型数组M，数组长度小于100，数组元素记录单个商品的价格，单个商品价格小于1000。
• 输入第二行为购买资金的额度R，R小于100000。
• 输入格式是正确的，无需考虑格式错误的情况。

输出描述

• 输出为满足上述条件的最大花费额度。
• 如果不存在满足上述条件的商品，请返回-1。

用例

题目解析

本题其实就是让我们从n个数中选择3个，保证这个3个数之和最接近且小于等于某个target。

解题思路是：

首先，我们将n个数的数组进行升序。

然后用三个指针I，L，R去指向数组的三个元素，形成三数组合，其中：

• I指针就是按照for循环遍历的顺序进行移动，从0~n-1
• L指针初始为 I + 1 位置
• R指针初始为 n – 1 位置

如下图所示：

其中 I 指针在每一轮循环中是位置固定的，我们需要移动L，R来找不大于，且最接近target的组合。L，R指针的移动逻辑如下：

假设 sum = arr[I] + arr[L] + arr[R]

• 如果sum == target了，则说明当前三个指针指向的元素组合就是不大于，且最接近target的答案，可以直接返回。
• 如果 sum < target，则说明三指针指向元素组合之和是一个可能解，但是不一定是最优解，此时我们应该先记录这个可能解，然后尝试将L++，由于arr已经升序了，因此L++后，新的三数组合之和一定比现在的大。
• 如果 sum > target，则说明三指针指向元素组合之和过大了，此时应该R–，这样新的三数组合之和一定比现在的小。

按此逻辑，将当前 I 指针固定的数的三数组合情况全部求出。

之后，再 I ++ ，尝试其他三数组合。

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    const arrM = lines[0].split(",").map(Number);
    const r = lines[1] - 0;
    console.log(getResult(arrM, r));
    lines.length = 0;
  }
});

function getResult(arr, target) {
  // 题目说小明要购买三件，如果商品不足三件直接返回-1
  if (arr.length < 3) return -1;

  // 数组升序
  arr.sort((a, b) => a - b);

  let ans = -1;

  for (let i = 0; i < arr.length; i++) {
    let l = i + 1;
    let r = arr.length - 1;

    while (l < r) {
      const sum = arr[i] + arr[l] + arr[r];

      if (sum == target) {
        return sum;
      } else if (sum < target) {
        ans = Math.max(ans, sum);
        l++;
      } else {
        r--;
      }
    }
  }

  return ans;
}

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

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

    Integer[] arrM =
        Arrays.stream(sc.nextLine().split(",")).map(Integer::parseInt).toArray(Integer[]::new);

    int r = Integer.parseInt(sc.nextLine());

    System.out.println(getResult(arrM, r));
  }

  // 算法入口
  public static int getResult(Integer[] arr, int target) {
    // 题目说小明要购买三件，如果商品不足三件直接返回-1
    if (arr.length < 3) return -1;

    // 数组升序
    Arrays.sort(arr);

    int ans = -1;

    for (int i = 0; i < arr.length; i++) {
      int l = i + 1;
      int r = arr.length - 1;

      while (l < r) {
        int sum = arr[i] + arr[l] + arr[r];
        if (sum == target) {
          return sum;
        } else if (sum < target) {
          ans = Math.max(ans, sum);
          l++;
        } else {
          r--;
        }
      }
    }

    return ans;
  }
}

Python算法源码

# 输入获取
arr = list(map(int, input().split(",")))
target = int(input())


# 算法入口
def getResult():
    # 题目说小明要购买三件，如果商品不足三件直接返回-1
    if len(arr) < 3:
        return -1

    # 数组升序
    arr.sort()

    ans = -1

    for i in range(len(arr)):
        l = i + 1
        r = len(arr) - 1

        while l < r:
            total = arr[i] + arr[l] + arr[r]

            if total == target:
                return total
            elif total < target:
                ans = max(ans, total)
                l += 1
            else:
                r -= 1

    return ans


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>

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

#define MAX_SIZE 100

int cmp(const void *a, const void *b);
int getResult(int nums[], int nums_size, int target);

int main() {
    int nums[MAX_SIZE];
    int nums_size = 0;

    while (scanf("%d", &nums[nums_size++])) {
        if (getchar() != ',') break;
    }

    int target;
    scanf("%d", &target);

    printf("%dn", getResult(nums, nums_size, target));

    return 0;
}

int getResult(int nums[], int nums_size, int target) {
    // 题目说小明要购买三件，如果商品不足三件直接返回-1
    if (nums_size < 3) return -1;

    // 数组升序
    qsort(nums, nums_size, sizeof(int), cmp);

    int ans = -1;

    for(int i=0; i<nums_size; i++) {
        int l = i + 1;
        int r = nums_size - 1;

        while(l < r) {
            int sum = nums[i] + nums[l] + nums[r];

            if(sum == target) {
                return sum;
            } else if(sum < target) {
                ans = MAX(ans, sum);
                l++;
            } else {
                r--;
            }
        }
    }

    return ans;
}

int cmp(const void *a, const void *b) {
    return (*(int *) a) - (*(int *) b);
}