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

(新卷,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("%d\n", 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); }