- 最大花费金额（Java JS Python C）)
(新卷,100分)- 最大花费金额（Java & JS & Python & C）
题目描述
双十一众多商品进行打折销售，小明想购买自己心仪的一些物品，但由于受购买资金限制，所以他决定从众多心仪商品中购买三件，而且想尽可能的花完资金。
现在请你设计一个程序帮助小明计算尽可能花费的最大资金数额。
输入描述
- 输入第一行为一维整型数组M，数组长度小于100，数组元素记录单个商品的价格，单个商品价格小于1000。
- 输入第二行为购买资金的额度R，R小于100000。
- 输入格式是正确的，无需考虑格式错误的情况。
输出描述
- 输出为满足上述条件的最大花费额度。
- 如果不存在满足上述条件的商品，请返回-1。
用例
| 输入 | 23,26,36,27
|
| 输出 | 76 |
| 说明 | 金额23、26和27相加得到76，而且最接近且小于输入金额78。 |
| 输入 | 23,30,40 26 |
| 输出 | -1 |
| 说明 | 因为输入的商品，无法组合出来满足三件之和小于26.故返回-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); }
