最大花费金额 - 华为OD统一考试

2023-12-31 17:23:10

OD统一考试

题解： Java / Python / C++

alt

题目描述

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

输入描述

第一行为一维整型数组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 (cost + prices[mid] <= R) {
                        left = mid;
                    } else {
                        right = mid;
                    }
                }

                // 更新最大花费
                maxCost = Math.max(maxCost, cost + prices[left]);
            }
        }

        System.out.println(maxCost);
    }
}

Python

prices = list(map(int, input().split(",")))
R = int(input())

prices.sort()
n = len(prices)

max_cost = -1
for i in range(n-2):
    for j in range(i + 1, n - 1):
        cost = prices[i] + prices[j]
        if cost + prices[j + 1] > R:  # 超过资金预算
            break

        # 二分尝试找到资金范围内最大的第三件商品
        left, right = j + 1, n
        while left + 1 < right:
            mid = (right + left) // 2
            if cost + prices[mid] <= R:
                left = mid
            else:
                right = mid

        # 购买 [i, j, left] 三件商品
        max_cost = max(max_cost, cost + prices[left])
print(max_cost)

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 输入价格列表, 资金预算
    vector<int> prices;
    int price, R;
    while (cin >> price) {
        prices.push_back(price);
        if(cin.peek() == ',') {
            cin.ignore();
        } else {
            cin >> R;
            break;
        }
    }


    // 对价格进行排序
    sort(prices.begin(), prices.end());

    int n = prices.size();
    int max_cost = -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 (cost + prices[mid] <= R) {
                    left = mid;
                } else {
                    right = mid;
                }
            }

            // 购买 [i, j, left] 三件商品
            max_cost = max(max_cost, cost + prices[left]);
        }
    }

    cout << max_cost << endl;

    return 0;
}

题号	题目	难易
LeetCode 167	167. 两数之和 II - 输入有序数组	中等
LeetCode 209	209. 长度最小的子数组	中等
LeetCode 1793	1793. 好子数组的最大分数	困难