4014. 应用折扣后的最低总价

题目描述

给你两个整数数组 prices 和 discounts。

prices[i] 表示第 i^th 件商品的价格，discounts[j] 表示一个折扣百分比。

你可以按照以下规则使用折扣：

每个折扣最多只能用于一件商品。
每件商品最多只能使用一个折扣。
商品也可以不使用任何折扣。

如果将 d% 的折扣应用于价格为 p 的商品，则其最终价格为 (p * (100 - d)) / 100。最终价格 不进行四舍五入 。

请以最优方式分配折扣，并返回所有商品最终价格之和的 最小值 。与实际答案的误差在 10^-5 以内的结果都将被接受。

示例 1：

输入： prices = [10,30,21], discounts = [50,60]

输出： 32.50000

解释：

将 discounts[1] = 60 应用于 prices[1] = 30，则最终价格为 30 * (100 - 60) / 100 = 12。
将 discounts[0] = 50 应用于 prices[2] = 21，则最终价格为 21 * (100 - 50) / 100 = 10.5。
prices[0] = 10 不使用折扣，因此价格仍为 10。

总价为 12 + 10.5 + 10 = 32.50000，这是可能得到的最小值。

示例 2：

输入： prices = [100,70], discounts = [10,40,50]

输出： 92.00000

解释：

将 discounts[2] = 50 应用于 prices[0] = 100，则最终价格为 100 * (100 - 50) / 100 = 50。
将 discounts[1] = 40 应用于 prices[1] = 70，则最终价格为 70 * (100 - 40) / 100 = 42。

总价为 50 + 42 = 92.00000，这是可能得到的最小值。

示例 3：

输入： prices = [7,3,9], discounts = [100,100]

输出： 3.00000

解释：

将 discounts[0] = 100 应用于 prices[2] = 9，则最终价格为 9 * (100 - 100) / 100 = 0。
将 discounts[1] = 100 应用于 prices[0] = 7，则最终价格为 7 * (100 - 100) / 100 = 0。
prices[1] = 3 不使用折扣，因此价格仍为 3。

总价为 0 + 0 + 3 = 3.00000，这是可能得到的最小值。

提示：

1 <= prices.length, discounts.length <= 10⁵
1 <= prices[i] <= 10⁵
1 <= discounts[j] <= 100

解法

方法一：贪心 + 排序

为了最小化总价，我们需要最大化折扣节省的总金额。若把折扣 \(d\) 应用于价格为 \(p\) 的商品，节省的金额为 \(p \times d / 100\)。根据排序不等式，把较大的折扣用在价格较高的商品上，可以使节省的总金额最大。

因此，我们将 \(\textit{prices}\) 和 \(\textit{discounts}\) 都按升序排序，然后用双指针从两个数组的末尾开始，依次把当前最大的折扣应用到当前最贵的商品上，并累加折后价格。当折扣用完后，剩余的商品按原价累加即可。

时间复杂度 \(O(n \times \log n + m \times \log m)\)，空间复杂度 \(O(\log n + \log m)\)。其中 \(n\) 和 \(m\) 分别是数组 \(\textit{prices}\) 和 \(\textit{discounts}\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def minPrice(self, prices: list[int], discounts: list[int]) -> float:
        prices.sort()
        discounts.sort()
        i, j = len(prices) - 1, len(discounts) - 1
        ans = 0
        while i >= 0 and j >= 0:
            ans += prices[i] * (100 - discounts[j]) / 100
            i -= 1
            j -= 1
        while i >= 0:
            ans += prices[i]
            i -= 1
        return ans

class Solution {
    public double minPrice(int[] prices, int[] discounts) {
        Arrays.sort(prices);
        Arrays.sort(discounts);

        int i = prices.length - 1;
        int j = discounts.length - 1;

        double ans = 0;

        while (i >= 0 && j >= 0) {
            ans += prices[i] * (100 - discounts[j]) / 100.0;
            i--;
            j--;
        }

        while (i >= 0) {
            ans += prices[i];
            i--;
        }

        return ans;
    }
}

class Solution {
public:
    double minPrice(vector<int>& prices, vector<int>& discounts) {
        sort(prices.begin(), prices.end());
        sort(discounts.begin(), discounts.end());

        int i = prices.size() - 1;
        int j = discounts.size() - 1;

        double ans = 0;

        while (i >= 0 && j >= 0) {
            ans += prices[i] * (100 - discounts[j]) / 100.0;
            i--;
            j--;
        }

        while (i >= 0) {
            ans += prices[i];
            i--;
        }

        return ans;
    }
};

func minPrice(prices []int, discounts []int) float64 {
    sort.Ints(prices)
    sort.Ints(discounts)

    i := len(prices) - 1
    j := len(discounts) - 1

    var ans float64

    for i >= 0 && j >= 0 {
        ans += float64(prices[i]) * float64(100-discounts[j]) / 100.0
        i--
        j--
    }

    for i >= 0 {
        ans += float64(prices[i])
        i--
    }

    return ans
}

function minPrice(prices: number[], discounts: number[]): number {
    prices.sort((a, b) => a - b);
    discounts.sort((a, b) => a - b);

    let i = prices.length - 1;
    let j = discounts.length - 1;

    let ans = 0;

    while (i >= 0 && j >= 0) {
        ans += (prices[i] * (100 - discounts[j])) / 100;
        i--;
        j--;
    }

    while (i >= 0) {
        ans += prices[i];
        i--;
    }

    return ans;
}

4014. 应用折扣后的最低总价

题目描述

解法

方法一：贪心 + 排序

评论