企业官网建设流程全解析

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完整代码如下：

packagemainimport("fmt""slices")funcminPrice(prices,discounts[]int)float64{slices.SortFunc(prices,func(a,bint)int{returnb-a})slices.SortFunc(discounts,func(a,bint)int{returnb-a})ans:=0fori,p:=rangeprices{d:=0ifi<len(discounts){d=discounts[i]}ans+=p*(100-d)}returnfloat64(ans)/100// 只做一次浮点运算}funcmain(){prices:=[]int{10,30,21}discounts:=[]int{50,60}result:=minPrice(prices,discounts)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-fromtypingimportListdefmin_price(prices:List[int],discounts:List[int])->float:prices=sorted(prices,reverse=True)discounts=sorted(discounts,reverse=True)ans=0fori,pinenumerate(prices):d=discounts[i]ifi<len(discounts)else0ans+=p*(100-d)returnans/100if__name__=="__main__":prices=[10,30,21]discounts=[50,60]result=min_price(prices,discounts)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>#include<numeric>doubleminPrice(std::vector<int>prices,std::vector<int>discounts){std::sort(prices.begin(),prices.end(),std::greater<int>());std::sort(discounts.begin(),discounts.end(),std::greater<int>());longlongans=0;for(size_t i=0;i<prices.size();++i){intd=(i<discounts.size())?discounts[i]:0;ans+=static_cast<longlong>(prices[i])*(100-d);}returnstatic_cast<double>(ans)/100.0;// 只做一次浮点运算}intmain(){std::vector<int>prices={10,30,21};std::vector<int>discounts={50,60};doubleresult=minPrice(prices,discounts);std::cout<<result<<std::endl;return0;}