推荐|【华为OD-E卷 -74 最大花费金额 100分（python、java、c++、js、c）】

【华为OD-E卷 - 最大花费金额 100分（python、java、c++、js、c）】

题目

双十一众多商品进行打折销售，小明想购买自己心仪的一些物品，但由于受购买资金限制，所以他决定从众多心仪商品中购买三件，而且想尽可能的花完资金。
现在请你设计一个程序帮助小明计算尽可能花费的最大资金数额

输入描述

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

输出描述

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

备注

用例

用例一：

输入：

23,26,36,27
78

输出：

用例二：

输入：

23,30,40
26

输出：

-1

python解法

解题思路：
本题的目标是找到一组三个人的价格组合，使得他们的总价尽可能接近给定的预算 budget，但是不超过预算。该问题本质上是一个三数之和问题。

输入：

一串价格数字，存储在列表 prices 中。
一个预算值 budget，我们需要找到三个价格之和尽量接近但不超过该预算。
处理步骤：

如果价格数量少于 3 个，则无法组成三人组合，直接返回 -1。
对价格列表进行排序，使得我们可以使用双指针法高效地遍历所有可能的组合。
使用三重循环的优化：
固定第一个价格 prices[i]，然后使用两个指针 left 和 right 来表示剩余两个价格的位置，分别指向当前 i 之后和列表末尾。
对于每一对 (prices[left], prices[right])，计算当前的和 current_sum = prices[i] + prices[left] + prices[right]：
如果 current_sum == budget，则直接返回该值，因为它正好等于预算。
如果 current_sum < budget，说明当前组合的总价太小，尝试增加 left 指针（即选择一个更大的数）。
如果 current_sum > budget，说明当前组合的总价太大，尝试减小 right 指针（即选择一个更小的数）。
在过程中记录当前的最大合法组合 max_spend，如果没有找到恰好等于预算的组合，最终返回最大合法组合。

prices = list(map(int, input().split(",")))  # 读取并转换输入的价格列表
budget = int(input())  # 读取预算

def find_max_spend():
    # 如果价格列表长度小于3，无法选出三个价格，直接返回-1
    if len(prices) < 3:
        return -1

    prices.sort()  # 将价格列表排序，方便使用双指针方法
    max_spend = -1  # 初始化最大支出为-1，表示没有合法组合

    # 外层循环：固定第一个价格
    for i in range(len(prices) - 2):
        left, right = i + 1, len(prices) - 1  # 定义双指针，left指向i后的第一个元素，right指向最后一个元素

        # 双指针法：在剩余的部分中查找两个数与prices[i]组合，计算三数和
        while left < right:
            current_sum = prices[i] + prices[left] + prices[right]  # 计算当前三数之和

            if current_sum == budget:  # 如果当前三数之和恰好等于预算，直接返回
                return current_sum
            if current_sum < budget:  # 如果当前和小于预算，说明需要增大当前和
                max_spend = max(max_spend, current_sum)  # 更新最大支出
                left += 1  # 移动左指针，尝试选择一个更大的数
            else:  # 如果当前和大于预算，说明需要减小当前和
                right -= 1  # 移动右指针，尝试选择一个更小的数

    return max_spend  # 返回最大合法支出

# 输出结果
print(find_max_spend())

java解法

解题思路
本题要求从一组价格中选择三个人，找出一个组合，其总价尽量接近给定的预算（不超过预算）。我们需要通过一种优化的算法来寻找这个组合，使得时间复杂度尽可能低。

本题本质上是一个三数之和问题，目标是找到三个数，它们的和尽量接近一个目标值（即预算）。

解题步骤
输入：

首先读取一组价格（以逗号分隔的数字），然后读取预算值。
处理：

边界条件检查：如果价格数组长度小于 3，无法选择 3 个价格，直接返回 -1。
排序：对价格进行排序，方便使用双指针法优化搜索过程。
双指针法：
外层循环固定一个价格 prices[i]，然后使用双指针法在剩余的部分（即 prices[i+1] 到 prices[prices.length-1]）中寻找另外两个价格，使得三个数的和尽量接近预算。
双指针调整：
计算当前三数之和 total = prices[i] + prices[left] + prices[right]。
如果当前和等于预算，返回该值。
如果当前和小于预算，说明当前的组合太小，增加 left（即选择更大的数）。
如果当前和大于预算，说明当前的组合太大，减小 right（即选择更小的数）。
记录最大合法值：如果没有找到正好等于预算的组合，记录最大合法组合 maxSpend，最终返回该值。
输出：

输出最大合法组合的总价，如果没有找到有效的组合，则返回 -1

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

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取价格列表并转换为 Integer 数组
        Integer[] prices = Arrays.stream(sc.nextLine().split(","))
                                 .map(Integer::parseInt)
                                 .toArray(Integer[]::new);
        
        // 读取预算值
        int budget = Integer.parseInt(sc.nextLine());
        
        // 调用函数计算最大支出并输出结果
        System.out.println(maxSpending(prices, budget));
    }

    // 计算不超过预算的最大支出
    public static int maxSpending(Integer[] prices, int budget) {
        // 如果价格列表长度少于 3，无法组成一个三人组合，返回 -1
        if (prices.length < 3) return -1;
        
        // 对价格进行排序，便于使用双指针方法
        Arrays.sort(prices);
        
        // 初始化最大支出值为 -1，表示没有找到合法组合
        int maxSpend = -1;

        // 外层循环，固定一个价格（i 从 0 到 prices.length-3）
        for (int i = 0; i < prices.length - 2; i++) {
            // 设置双指针，left 指向 i+1，right 指向数组末尾
            int left = i + 1;
            int right = prices.length - 1;
            
            // 使用双指针寻找剩余两数
            while (left < right) {
                // 计算当前三数之和
                int total = prices[i] + prices[left] + prices[right];

                // 如果当前三数之和恰好等于预算，直接返回该值
                if (total == budget) {
                    return total;
                } 
                
                // 如果三数和小于预算，说明需要增大组合总和，左指针右移
                else if (total < budget) {
                    maxSpend = Math.max(maxSpend, total); // 更新最大合法支出
                    left++; // 移动左指针
                } 
                
                // 如果三数和大于预算，说明需要减小组合总和，右指针左移
                else {
                    right--; // 移动右指针
                }
            }
        }
        
        // 返回最大合法支出，如果没有找到合法组合，返回 -1
        return maxSpend;
    }
}

C++解法

解题思路
本题的目标是从一个价格列表中选择三个数，使得这三数之和尽量接近给定的预算（不超过预算）。要求输出三个数的和，如果没有符合条件的组合，返回 -1。

我们可以通过以下步骤来解决这个问题：

输入处理：

第一行是一个逗号分隔的字符串，表示各个商品的价格。
第二行是预算值，表示消费者能接受的最大支出。
问题分析：

由于要从多个价格中选择三个数，我们可以将问题转化为三数之和问题，目标是找到三个数，它们的和尽量接近预算，并且不超过预算。
可以使用双指针法来优化搜索。排序后，固定一个元素，使用双指针扫描剩下的部分，快速找到符合条件的三数之和。
算法步骤：

排序：首先对价格数组进行升序排序，排序的目的是为了后续使用双指针法来高效寻找三数之和。
双指针法：
外层循环遍历每个元素，将其作为当前三数之和的第一个数。
内层使用两个指针，left 指向当前元素的下一个位置，right 指向数组的最后一个位置。通过调整 left 和 right 来寻找与当前元素配对的另两个数，使得三数之和尽量接近预算。
更新最大值：如果找到的三数之和小于预算，更新最大合法支出；如果三数之和等于预算，直接返回该值。
如果没有找到合适的组合，返回最大合法支出或 -1

#include 
#include 
#include 
#include 

using namespace std;

// 函数用于查找不超过预算的最大支出
int findMaxSpending(vector<int>& prices, int budget) {
    // 如果价格数组长度小于3，不能选择3个价格，直接返回-1
    if (prices.size() < 3) return -1;

    // 初始化最大支出为-1，表示没有找到合法组合
    int maxSpend = -1;

    // 对价格数组进行排序，以便使用双指针法
    sort(prices.begin(), prices.end());

    // 外层循环：遍历每个价格，固定一个价格
    for (int i = 0; i < prices.size() - 2; i++) {
        // 使用双指针法，left指向当前元素的下一个位置，right指向数组的最后一个位置
        int left = i + 1;
        int right = prices.size() - 1;

        // 使用双指针扫描剩余的部分
        while (left < right) {
            // 计算当前三数之和
            int sum = prices[i] + prices[left] + prices[right];

            // 如果当前三数之和正好等于预算，直接返回该值
            if (sum == budget) {
                return sum;
            }
            // 如果三数和小于预算，说明需要增大总和，移动左指针
            else if (sum < budget) {
                // 更新最大合法支出
                maxSpend = max(maxSpend, sum);
                left++;  // 左指针右移，尝试增大总和
            }
            // 如果三数和大于预算，说明需要减小总和，移动右指针
            else {
                right--;  // 右指针左移，尝试减小总和
            }
        }
    }

    // 返回最大合法支出，如果没有找到合法组合，则返回-1
    return maxSpend == -1 ? -1 : maxSpend;
}

int main() {
    // 读取价格输入（逗号分隔的字符串）
    string pricesInput;
    getline(cin, pricesInput);

    // 读取预算输入
    string budgetInput;
    getline(cin, budgetInput);

    // 将价格字符串转换为整数数组
    vector<int> prices;
    stringstream ss(pricesInput);
    string temp;

    while (getline(ss, temp, ',')) {
        prices.push_back(stoi(temp));  // 将每个价格字符串转换为整数并加入到数组
    }

    // 将预算转换为整数
    int budget = stoi(budgetInput);

    // 调用函数计算最大支出并输出结果
    cout << findMaxSpending(prices, budget) << endl;

    return 0;
}

C解法

解题思路

更新中

JS解法

解题思路
本题的目标是给定一个价格列表和一个预算值，要求从价格列表中选择三个不同的商品，使得这三个商品的价格之和尽量接近预算并且不超过预算。如果没有符合条件的组合，返回 -1。

解决方案
输入处理：

第一行是一个逗号分隔的字符串，表示商品的价格列表。
第二行是一个整数，表示预算。
核心思路：

三数之和问题：这是一个经典的算法问题，目标是从给定的数组中选出三个数，使得它们的和尽量接近目标值（即预算）。
排序 + 双指针法：首先将价格数组排序。然后固定一个元素（作为当前三数和的第一个元素），再通过双指针法来寻找另外两个元素，使得三数之和尽量接近预算。
双指针法的具体步骤：固定当前元素后，使用两个指针分别指向当前元素之后的位置和数组的最后位置：
如果三数之和小于预算，则增加左指针（左边的数增大可能使和更接近预算）。
如果三数之和大于预算，则减少右指针（右边的数减小可能使和更接近预算）。
每次都计算当前三数之和，并记录一个合法的最大和。
返回结果：如果找到符合条件的组合，则返回最大合法和。如果没有找到，返回 -1

const readline = require("readline");

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

// 存储输入的行
let lines = [];

// 监听每一行输入
rl.on("line", (input) => {
  lines.push(input); // 将输入行存入数组
  // 当输入两行时，开始处理
  if (lines.length === 2) {
    // 第一行：商品价格列表，第二行：预算
    const prices = lines[0].split(",").map(Number); // 将价格字符串转换为数字数组
    const budget = Number(lines[1]); // 将预算字符串转换为数字
    console.log(findMaxSpending(prices, budget)); // 调用函数并输出结果
    lines = []; // 清空输入行，准备下一轮输入
  }
});

// 核心函数：找出三个商品的最大支出
function findMaxSpending(prices, budget) {
  // 如果价格列表中商品少于3个，不能选择三种商品，返回-1
  if (prices.length < 3) return -1;

  let maxSpend = -1; // 初始化最大支出为-1，表示未找到符合条件的组合

  // 对价格数组进行升序排序
  prices.sort((a, b) => a - b);

  // 遍历每个元素，作为三数之和的第一个数
  for (let i = 0; i < prices.length - 2; i++) {
    // 使用双指针法，左指针指向当前元素的下一个位置，右指针指向数组的最后一个位置
    let left = i + 1;
    let right = prices.length - 1;

    // 双指针法：如果左指针小于右指针，则继续循环
    while (left < right) {
      const sum = prices[i] + prices[left] + prices[right]; // 计算三数之和

      // 如果三数之和等于预算，直接返回
      if (sum === budget) {
        return sum;
      } 
      // 如果三数之和小于预算，说明需要增大总和，左指针右移
      else if (sum < budget) {
        maxSpend = Math.max(maxSpend, sum); // 更新最大支出
        left++; // 左指针右移，增大当前和
      } 
      // 如果三数之和大于预算，说明需要减小总和，右指针左移
      else {
        right--; // 右指针左移，减小当前和
      }
    }
  }

  // 如果没有找到合适的三数之和，返回最大合法支出，否则返回-1
  return maxSpend === -1 ? -1 : maxSpend;
}

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏