北京
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 / 100if __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助力您的未来发展。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
