刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

题目描述:

(注.input()输入函数的括号中不允许添加任何信息)

时间限制:3000MS 内存限制:589824KB

编程实现:

某商店搞促销活动“买二免一”,活动内容如下:

每买两件商品,结算时只收取其中价格高的商品费用,另一件商品不收取费用(相同价格只收取一件商品费用)。

小明选购了N件商品(2<=N<=1000,N为偶数),且已知每件商品的价格。请帮助小明,把商品进行两两组合,使得购买花费最少,并输出总费用。

例如:

N=6,6件商品价格分别为32、56、92、45、12、98,共结算3次。

当98与92组合,56与45组合,32与12组合时,花费最少,总费用为186(186=98+56+32)。

输入描述

第一行输入一个正整数N(2≤N≤1000,N为偶数),表示小明选购的商品数量

第二行输入N个正整数(1≤正整数≤100),表示每件商品的价格,正整数之间以一个英文逗号隔开

输出描述

输出一个整数,表示购买N件商品最少需要花费的钱数


样例输入

6
32,56,92,45,12,98

样例输出

186

使用微信搜索喵呜刷题,轻松应对考试!

答案:

br />根据题目要求,我们可以先将商品按价格从高到低进行排序,然后从最高价开始,每两个商品为一组,若这两件商品的价格相同,则只收取一件商品的费用。最后将所有收取的费用累加即可得到最少花费。

解析:

【喵呜刷题小喵解析】
根据题目描述,我们可以将问题转化为一个贪心算法问题。首先将商品按照价格从高到低进行排序,然后从最高价开始,每两个商品为一组,若这两件商品的价格相同,则只收取一件商品的费用。最后将所有收取的费用累加即可得到最少花费。由于题目要求商品数量必须为偶数,因此在排序时只需考虑前N/2个商品即可。具体实现时,可以使用一个循环遍历商品列表,每两个商品为一组进行处理,统计最终的花费即可。时间复杂度为O(NlogN),其中N为商品数量。
创作类型:
原创

本文链接:题目描述: (注.input()输入函数的括号中不允许添加任何信息) 时间限制:3000MS 内存限

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share