某商店搞促销活动“买二免一”,活动内容如下: 每买两件商品,结算时只收取其中价格高的商品费用,另一件商品不收取费用(相同价格只收取一件商品费用)。 小明选购了N件商品(2≤N≤1000,N为偶数),且已知每件商品的价格。请帮助小明,把商品进行两两组合,使得购买花费最少,并输出总费用。
时间: 2023-11-14 22:06:07 浏览: 176
商店促销活动中的付费问题
这是一个经典的贪心算法问题,具体思路如下:
1.将商品价格从小到大排序;
2.按照排序后的顺序两两组合,每组中取价格较高的商品计入总费用;
3.输出总费用即可。
下面是一个简单的 Python 实现:
```
n = int(input())
prices = list(map(int, input().split()))
prices.sort()
total_cost = 0
for i in range(n//2):
total_cost += prices[2*i+1]
print(total_cost)
```
其中,`n` 表示商品数量,`prices` 是一个列表,存储每个商品的价格。首先使用 `sort()` 方法将价格排序,然后按照上述算法进行操作,最后输出总费用。
阅读全文