最大花费金额 - 华为OD统一考试
OD统一考试
题解: Java / Python / C++
题目描述
双十一众多商品进行打折销售,小明想购买自己心仪的一些物品,但由于受购买资金限制,所以他决定从众多心仪商品中购买三件,而且想尽可能的花完资金现在请你设计一个程序帮助小明计算尽可能花费的最大资金数额。
输入描述
第一行为一维整型数组M,数组长度Q小于100,数组元素记录单个商品的价格,单个商品价格小于1000。
第二行为购买资金的额度R,R小于100000。
输出描述
输出为满足上述条件的最大花费额度
如果不存在满足上述条件的商品,请返回-1。
示例1
输入:
23,26,36,27
78
输出:
76
说明:
金额23、26和27相加得到76,而且最接近且小于输入金额78。
示例2
输入:
10,2,3,4,5,6,7,30
20
输出:
20
题解
解题思路:
该问题可以通过排序数组,然后使用双指针和二分查找的方法来求解。首先,对商品价格进行排序。然后,使用两个循环遍历可能的商品组合(三个商品),并使用二分查找找到第三个商品,使得总花费最接近但不超过购买资金限制。
时间复杂度: 两个循环的嵌套加二分总体时间复杂度为 O(n^2 log n)。
Java
import java.util.Arrays;
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取输入数组
String[] pricesString = scanner.nextLine().split(",");
int[] prices = Arrays.stream(pricesString).mapToInt(Integer::parseInt).toArray();
// 读取输入的 R
int R = Integer.parseInt(scanner.nextLine());
// 排序数组
Arrays.sort(prices);
int n = prices.length, maxCost = -1;
// 遍历组合
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
int cost = prices[i] + prices[j];
if (cost + prices[j + 1] > R) {
break;
}
// 二分查找
int left = j + 1, right = n;
while (left + 1 < right) {
int mid = (right + left) / 2;
if (co
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试真题题解 文章被收录于专栏
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。