HDU 1678 Shopaholic(排序)
发布日期:2021-11-06 16:56:41
浏览次数:2
分类:技术文章
本文共 2040 字,大约阅读时间需要 6 分钟。
Shopaholic
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1603 Accepted Submission(s): 900 Problem Description
Lindsay is a shopaholic. Whenever there is a discount of the kind where you can buy three items and only pay for two, she goes completely mad and feels a need to buy all items in the store. You have given up on curing her for this disease, but try to limit its effect on her wallet. You have realized that the stores coming with these offers are quite elective when it comes to which items you get for free; it is always the cheapest ones. As an example, when your friend comes to the counter with seven items, costing 400, 350, 300, 250, 200, 150, and 100 dollars, she will have to pay 1500 dollars. In this case she got a discount of 250 dollars. You realize that if she goes to the counter three times, she might get a bigger discount. E.g. if she goes with the items that costs 400, 300 and 250, she will get a discount of 250 the first round. The next round she brings the item that costs 150 giving no extra discount, but the third round she takes the last items that costs 350, 200 and 100 giving a discount of an additional 100 dollars, adding up to a total discount of 350. Your job is to find the maximum discount Lindsay can get.
Input
The first line of input gives the number of test scenarios, 1 <= t <= 20. Each scenario consists of two lines of input. The first gives the number of items Lindsay is buying, 1 <= n <= 20000. The next line gives the prices of these items, 1 <= pi <= 20000.
Output
For each scenario, output one line giving the maximum discount Lindsay can get by selectively choosing which items she brings to the counter at the same time.
Sample Input
16400 100 200 350 300 250
Sample Output
400
题意:买3样东西,最便宜的那样可以不用付钱。问n样东西最多不用付多少?
AC代码:#include#include #include using namespace std; int a[20010];bool cmp(int a,int b){ return a>b;}int main(){ int t,n,i,sum; scanf("%d",&t); while(t--){ scanf("%d",&n); for(i=0;i
转载地址:https://blog.csdn.net/YJX_xx/article/details/37659691 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
网站不错 人气很旺了 加油
[***.192.178.218]2024年04月06日 22时08分43秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
java自学笔记
2019-04-26
聊一聊,单元测试应该测试什么?
2019-04-26
史上最便捷搭建RocketMQ服务器的方法
2019-04-26
初学java的你,是不是很迷茫?
2019-04-26
如何系统的自学java?
2019-04-26
java零基础自学网站分享
2019-04-26
零基础自学java,能否学会?要不要报培训班?
2019-04-26
零基础自学java,如何找学习资料
2019-04-26
给java初学者的一些建议
2019-04-26
java初学者问题------能看懂,不会写怎么办?
2019-04-26
2020最新java面试题精讲(面试必备)
2019-04-26
java零基础如自学入门,顺利找到高薪工作!
2019-04-26
21 个刁钻的 HashMap 面试题,这次要跪了!
2019-04-26
分布式与集群的区别到底是什么?
2019-04-26
1.5W 字搞懂 Spring Cloud,太牛了!
2019-04-26
轻松上手 Spring Boot & Kafka 实战!
2019-04-26
你知道Spring Boot如何 发邮件和附件吗?超实用!赶紧收藏起来吧!
2019-04-26
推荐一款 IDEA 生成代码神器,写代码再也不用加班了!
2019-04-26
零基础阿里云服务器入门(新用户)
2019-04-26
服务器入门
2019-04-26