2026-11-03：应用折扣后的最低总价。用go语言，有商品价格数组和折扣百分比数组。价格数组中的每个元素表示一件商品的标价，折扣数组中的

2026-11-03：应用折扣后的最低总价。用go语言，有商品价格数组和折扣百分比数组。价格数组中的每个元素表示一件商品的标价，折扣数组中的每个元素表示一种可选的降价比例。分配折扣时需满足：一种折扣最多作用于一件商品，一件商品最多接受一种折扣，商品也可以不参与折扣。若某商品原价为 p，使用百分比为 d 的折扣，则结算价按 p 乘以（100 减 d）再除以 100 计算，结果保留精确值，不做四舍五入。目标是合理选择哪些商品使用哪些折扣，使全部商品的结算价总和尽可能小，并返回这个最小总和。答案允许存在一定数值误差，绝对或相对误差在 10 的负 5 次方以内均可接受。

1 <= prices.length, discounts.length <= 100000。

1 <= prices[i] <= 100000。

1 <= discounts[j] <= 100。

输入： 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，这是可能得到的最小值。

题目来自力扣4014。

分步骤描述过程

1.理解目标

• 对每个商品，可以选择不使用折扣，或使用某一个折扣。

• 每个折扣最多用一次，每件商品最多用一个折扣。

• 若商品原价为p，使用折扣百分比为d，则折后价为
p * (100 - d) / 100。

• 目标是让所有商品的折后价总和最小。

• 因为总原价固定，所以等价于让“节省的总金额”最大。某商品使用折扣d节省的金额是p * d / 100。因此价格越高的商品，越应该搭配越大的折扣。

2.对价格数组降序排序

• 代码首先把prices按从大到小排序。

• 排序后，价格最高的商品排在最前面。

• 这样后续可以优先给高价格商品分配较大的折扣。

3.对折扣数组降序排序

• 代码同样把discounts按从大到小排序。

• 排序后，折扣力度最大的折扣排在最前面。

• 折扣百分比越大，表示降价越多。

4.按顺序一一配对

• 遍历排序后的价格数组。

• 对于第i个价格：

• 如果i还没有超过折扣数组长度，就取排序后第i个折扣，即当前可用的最大折扣，分配给当前价格。

• 如果折扣已经用完，则当前商品不使用折扣，等价于折扣百分比为0。

• 因为价格和折扣都按降序排列，所以实际上就是：

• 最高价格配最大折扣；

• 第二高价格配第二大折扣；

• 依此类推；

• 折扣数量不足时，剩余商品原价结算；

• 折扣数量多于商品数量时，多出来的折扣不使用。

5.累加折后价格的“百分比分子”

• 对每个商品，代码没有立即做除法，而是先计算：

•p * (100 - d)

• 这相当于该商品折后价乘以100后的结果。

• 把所有商品的这个值累加到ans中。

• 这样做可以避免每件商品单独除法带来的浮点误差，最后只做一次除法。

6.最后一次性转换为实际总价

• 遍历结束后，ans表示所有商品折后总价乘以100的结果。

• 最后返回ans / 100的浮点结果。

• 因为除法只在最后做一次，所以精度较好，符合题目允许误差的要求。

7.示例验证

• 输入价格：[10, 30, 21]

• 输入折扣：[50, 60]

• 价格降序后：[30, 21, 10]

• 折扣降序后：[60, 50]

• 配对：

•30配60，折后为30 * 40 / 100 = 12

•21配50，折后为21 * 50 / 100 = 10.5

•10没有折扣，折后仍为10

• 总价为12 + 10.5 + 10 = 32.5

• 与题目输出一致。

8.贪心为什么正确

• 假设有两个价格p1 >= p2，两个折扣d1 >= d2。

• 如果让大价格配大折扣，节省金额为：

•p1 * d1 + p2 * d2

• 如果反过来，小价格配大折扣，节省金额为：

•p1 * d2 + p2 * d1

• 两者之差为：

•(p1 - p2) * (d1 - d2)

• 因为p1 >= p2且d1 >= d2，所以这个差大于等于0。

• 因此，大价格配大折扣不会比反过来差，贪心策略正确。

时间复杂度

设价格数组长度为n，折扣数组长度为m。

• 对价格数组排序：O(n log n)

• 对折扣数组排序：O(m log m)

• 遍历价格数组累加：O(n)

因此总时间复杂度为：

O(n log n + m log m)

额外空间复杂度

• 算法没有创建与n或m同阶的新数组，排序是原地进行的。

• 但排序算法内部通常需要递归栈等辅助空间：

• 价格排序约O(log n)

• 折扣排序约O(log m)

• 因此若把排序内部栈计入，额外空间复杂度为：

O(log n + log m)

如果只统计代码中显式申请的额外数组空间，则除排序内部开销外为O(1)。

Go完整代码如下：

package main

 import (
    "fmt"
    "slices"
)

 func minPrice(prices, discounts []int)float64 {
    slices.SortFunc(prices, func(a, b int)int { return b - a })
    slices.SortFunc(discounts, func(a, b int)int { return b - a })

     ans := 0
    for i, p := range prices {
        d := 0
        if i < len(discounts) {
            d = discounts[i]
        }
        ans += p * (100 - d)
    }
    returnfloat64(ans) / 100// 只做一次浮点运算
}

 func main() {
    prices := []int{10, 30, 21}
    discounts := []int{50, 60}
    result := minPrice(prices, discounts)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def min_price(prices: List[int], discounts: List[int]) -> float:
    prices = sorted(prices, reverse=True)
    discounts = sorted(discounts, reverse=True)

     ans = 0
    for i, p in enumerate(prices):
        d = discounts[i] if i < len(discounts) else0
        ans += p * (100 - d)

     return ans / 100

 if __name__ == "__main__":
    prices = [10, 30, 21]
    discounts = [50, 60]
    result = min_price(prices, discounts)
    print(result)

C++完整代码如下：

  

  

    


 double minPrice(std::vector prices, std::vector discounts) {
    std::sort(prices.begin(), prices.end(), std::greater());
    std::sort(discounts.begin(), discounts.end(), std::greater());

     long long ans = 0;
    for (size_t i = 0; i < prices.size(); ++i) {
        int d = (i < discounts.size()) ? discounts[i] : 0;
        ans += static_cast 
 
 (prices[i]) * ( 
 100 - d);
    }
    return static_cast 
 
 (ans) /  
 100.0; // 只做一次浮点运算
}

 int main() {
    std::vector prices = {10, 30, 21};
    std::vector discounts = {50, 60};
    double result = minPrice(prices, discounts);
    std::cout << result << std::endl;
    return0;
}

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。