注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

购书(gs) [nhoi 2016 T1]  

2016-06-12 13:51:51|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
【题目描述】
书店稿促销优惠活动:“卖 3 本免费 1 本”。即如果你买 3 本书,价格最便宜的那本书就不收钱。
如果买很多书,不同分组优惠的价格可能不同。比如,买 7 本书,价格分别是:10,3,2,4,6,4,9。如果分
组是:(10,3,2),(4,6,4)和(9),第一组免费价格 2,第二组免费价格 4,第三组不能免费。
现在,你买了 N 本书,请恰当分组(每组 1 本到 3 本),使得花费最少?
【输入格式】
第一行包含 1 个整数 N,1≤N≤100000。
下面 N 行,每行 1 个整数 Ci 表示一本书的价格。1≤ Ci ≤ 100000。
【输出格式】
一个整数,最少付款是多少。
【数据范围】
50% N≤2000。
============================================
        第一题嘛,大贪心。所谓贪心,步步为赢。三本书中最便宜的不用给钱,那么n本书中,肯定是要有n/3本书可以免费。最贵的和第二贵的怎么也免不了,那就按贪心来说,那就免第三贵的那本,然后免第六,第九……因此,只需排序后隔三个不加一个,隔三个不加一个,就行了,为什么呢
        排序后,1,2,3,4,5,6……,试着分两组,第一组可以省去≥3,≤5的,最好也就是省去3;第二组可以省去≥6的,最好就是省去6。不然,第一组省去了一个≥6的,第二组就可以省去5了,但……明显……并没有什么用。所以,省去3和6是最优的。
============================================

//CY137 yhf

#include <algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

const int ML=100010;

int a[ML];

int main()
{
freopen("gs.in","r",stdin);
freopen("gs.out","w",stdout);

int n; scanf("%d",&n);

for (int i=0; i<n; i++) //scanf读入不解释
scanf("%d",&a[i]);

sort(a+0,a+n);

long long sum=0,ans=0; //不用long long会爆不解释

for (int i=n-1; i>=0; i--)
{
sum++;
if (sum%3>0) ans+=a[i]; //脑残写法不解释
}

cout<<ans;

return 0;
}


  评论这张
 
阅读(2)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018