给定n个怪物,每次攻击能对一个敌人造成1点伤害,当一个敌人血量降到一半及以下时,会对所有敌人都造成一点伤害,求最少需要的攻击次数。
看完题面后,一个很直观的想法是,为了能尽量少的攻击,要将天赋效果尽可能发挥满。也就是说,如果一个敌人能被天赋效果aoe死,我们就不打他了。
而aoe触发次数是固定的n次,所以我们的任务就是决定怪物触发aoe的顺序,以及所有怪触发完aoe后的补刀。
米小游最近沉迷于一款割草游戏。所谓割草游戏,并不是割草模拟器,而是指一款击杀敌人快,很容易一次性就击杀大量敌人的游戏。
米小游每放一个大范围aoe技能下去,就能看见屏幕上一大片的敌人消失,非常解压。
这天,米小游又在玩这款割草游戏了,他看着面前的n个敌人,每个敌人都有ai的血,但是突然发现他的技能只能给一个敌人造成1点伤害了。但好在米小游所使用的角色点了天赋,开局时给所有敌人添加debuff,当一名敌人血量降到一半及以下时,就会给所有敌人造成1点伤害(这个debuff触发一次后消失)。米小游想知道,他最少需要多少次攻击才能击杀所有敌人。
第一行输入一个正整数n,代表敌人的最大数量
第二行输入n个正整数ai,代表每个敌人的血量
1≤n≤105
1≤ai≤109
一个正整数,代表米小游攻击的最小次数。
输入
2
6 8
输出
10
说明
米小游打第一个敌人3次,触发天赋,每个敌人剩余2,7血。接下来,米小游打第二个敌人3次,触发天赋,每个敌人剩余1,3血。米小游无法再触发天赋了,因此还要攻击4次,总共是10次。
输入
4
1 2 4 4
输出
1