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。分步骤描述过程理解目标对每个商品可以选择不使用折扣或使用某一个折扣。每个折扣最多用一次每件商品最多用一个折扣。若商品原价为p使用折扣百分比为d则折后价为p * (100 - d) / 100。目标是让所有商品的折后价总和最小。因为总原价固定所以等价于让“节省的总金额”最大。某商品使用折扣d节省的金额是p * d / 100。因此价格越高的商品越应该搭配越大的折扣。对价格数组降序排序代码首先把prices按从大到小排序。排序后价格最高的商品排在最前面。这样后续可以优先给高价格商品分配较大的折扣。对折扣数组降序排序代码同样把discounts按从大到小排序。排序后折扣力度最大的折扣排在最前面。折扣百分比越大表示降价越多。按顺序一一配对遍历排序后的价格数组。对于第i个价格如果i还没有超过折扣数组长度就取排序后第i个折扣即当前可用的最大折扣分配给当前价格。如果折扣已经用完则当前商品不使用折扣等价于折扣百分比为0。因为价格和折扣都按降序排列所以实际上就是最高价格配最大折扣第二高价格配第二大折扣依此类推折扣数量不足时剩余商品原价结算折扣数量多于商品数量时多出来的折扣不使用。累加折后价格的“百分比分子”对每个商品代码没有立即做除法而是先计算p * (100 - d)这相当于该商品折后价乘以100后的结果。把所有商品的这个值累加到ans中。这样做可以避免每件商品单独除法带来的浮点误差最后只做一次除法。最后一次性转换为实际总价遍历结束后ans表示所有商品折后总价乘以100的结果。最后返回ans / 100的浮点结果。因为除法只在最后做一次所以精度较好符合题目允许误差的要求。示例验证输入价格[10, 30, 21]输入折扣[50, 60]价格降序后[30, 21, 10]折扣降序后[60, 50]配对30配60折后为30 * 40 / 100 1221配50折后为21 * 50 / 100 10.510没有折扣折后仍为10总价为12 10.5 10 32.5与题目输出一致。贪心为什么正确假设有两个价格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(fmtslices)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:0ifilen(discounts){ddiscounts[i]}ansp*(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:pricessorted(prices,reverseTrue)discountssorted(discounts,reverseTrue)ans0fori,pinenumerate(prices):ddiscounts[i]ifilen(discounts)else0ansp*(100-d)returnans/100if__name____main__:prices[10,30,21]discounts[50,60]resultmin_price(prices,discounts)print(result)C完整代码如下#includeiostream#includevector#includealgorithm#includenumericdoubleminPrice(std::vectorintprices,std::vectorintdiscounts){std::sort(prices.begin(),prices.end(),std::greaterint());std::sort(discounts.begin(),discounts.end(),std::greaterint());longlongans0;for(size_t i0;iprices.size();i){intd(idiscounts.size())?discounts[i]:0;ansstatic_castlonglong(prices[i])*(100-d);}returnstatic_castdouble(ans)/100.0;// 只做一次浮点运算}intmain(){std::vectorintprices{10,30,21};std::vectorintdiscounts{50,60};doubleresultminPrice(prices,discounts);std::coutresultstd::endl;return0;}