【NOIP模拟赛】肥得更高

2014年10月18日1,4541

背景

自2009年以来,A、B站的历史就已经步入了农业变革的黎明期。
在两站的娱乐及音乐区,金坷垃制造业早已得到长足的发展,甚至有些地方还出现了坷垃翻唱的萌芽。
新兴肥料人开始走上历史的舞台。
他们需要新的意识形态,来为他们所追求的肥料辩护;
他们需要新的理念、新的手段,来为金坷垃的生产提供支持。
这样,一种崭新的肥料精神就诞生了。
肥料复兴,是反对肥料粗制滥造,追求创新的新肥料文化的运动。
它必将成为推动金坷垃走得更远、飞得更高的重要力量。

描述

现在,你有n亩的小麦地需要增产,你拥有一些金坷垃,但是金坷垃极其稀少,掺肥料也只够你撒K次。

众所周知,金坷垃能激活土壤深处的氮磷钾,同一块地可以撒多次肥料,但是效果是有略微衰减的。

实地考察后你发现,第i亩土地第x次撒肥料增产a[i]-x+1公斤。

hzwer将代替你去撒肥料,但是他是个蒟蒻,完全不动大脑,所以你想知道如果他随机撒肥料,最坏情况下小麦将增产多少,最好情况下将增产多少?(他最多只会对第i亩地撒肥料a[i]次)

输入格式

第一行两个整数n,K

第二行n个整数,第i个整数为a[i]

输出格式

输出最大值,最小值,空格隔开

样例数据 1

输入  [复制]

5 10
10 3 3 1 2

输出

58 26

备注

对于30%的数据n,k<=1000

对于70%的数据n,k<=200000

对于100%的数据n,k,a[i]<=1000000

题解

显然每次都取a[i]的最大值/最小值,并更新a[i]即可

用数据结构维护这一操作。。得分看常数

事实上用v[i]记录权值为i的个数,然后for乱搞就可以了。。。不过我懒得写了。。。

其它乱搞做法能获得不同的分数

提供一种50分解法

排序后

最小值,从左依次取到0

最大值,一直取最右的那个,如果它变得比前面的小就交换位置。。。

把最大值的做法改成pq维护的话就能随便水过了

 

  • 黄维2015年10月19日 下午3:27 回复

    肥料掺了金坷垃,一袋能顶两袋撒

    #1