买二赠一。

大家好，欢迎来到IT知识分享网。

问题描述
某商场有N件商品，其中第件的价格是A。现在该商场正在进行“买二赠一”的优惠活动，具体规则是:每购买2件商品，假设其中较便宜的价格是P(如果两件商品价格一样，则P等于其中一件商品的价格)，就可以从剩余商品中任选一件价格不超过的商品，免费获得这一件商品。可以通过反复购买2件商品来获得多件免费商品，但是每件商品只能被购买或免费获得一次。
小明想知道如果要拿下所有商品(包含购买和免费获得)，全少要花费多少钱?
输入格式
第一行包含一个整数N
第二行包含N 个整数，代表 A1,A2,A3,…,AN。
输出格式
输出一个整数，代表答案
样例输入

7

样例输出
25

import os import sys # 请在此输入您的代码 n = int(input()) price = list(map(int, input().split())) price.sort() money = sum(price) cnt = 0 #cnt 表示当前已经购买的商品数量 free = n - 1 #free 表示剩余可以享受折扣的商品索引 for i in range(n - 1, -1, -1): #n-1是因为索引从0到n-1 if price[i] == 0: continue if cnt == 0: #一次要买两个，要跳过第一个价格高的 cnt += 1 continue half = price[i] // 2 #计算当前商品价格的一半 while free >= 0 and price[free] > half: #找出小于价格一半的免费商品 free -= 1 if free < 0: break money -= price[free] #减去免费的钱 price[free] = 0 #免费商品价格为0 cnt = 0 free = free - 1 print(money)