/ TYWZ / 题库 /

sapling

sapling

题目描述

在游戏Minecraft中,玩家可以通过种树来使木材再生。玩家需要将树苗种在泥土上,然后等待它长成大树,期间可以利用骨粉来催熟树苗。
Steve种了nn棵树苗,自然状态下第ii棵树苗长成大树需要的时间为ti t_i 分钟。由于骨粉不容易获取,Steve每分钟至多只会用1瓶骨粉。每瓶骨粉可以使一棵树苗的剩余生长时间减少kk分钟。如果该树苗的剩余生长时间k\le k,那么它会立刻长成大树。
合理规划骨粉的使用,可以使所有树苗长成大树所需的时间减少。求:最少需要等待多少分钟,所有的树苗都能长成大树?

格式

输入格式

第一行是一个正整数nn
第二行是nn个正整数,表示自然状态下各个树苗成熟需要的时间ti t_i
第三行是一个非负整数kk

输出格式

一个正整数,最少需要等待的分钟数。

样例

输入

3
2 3 9
5

输出

数据规模及限制

时间限制1s,空间限制64MB
共10组测试数据。所有数据均满足0k1050 \le k \le 10^5
测试点#1 ~ #2:n10n \le 10ti20 t_i \le 20
测试点#3 ~ #4:n1000n \le 1000ti2000 t_i \le 2000
测试点#5 ~ #6:n105n \le 10^5ti2×105 t_i \le 2 \times 10^5
测试点#7 ~ #10:n105n \le 10^5ti109 t_i \le 10^9

来源

2017.7 太原五中高一集训
From: PKU Online Judge

信息

难度
8
分类
贪心 | 二分查找 点击显示
标签
(无)
递交数
189
已通过
15
通过率
8%
上传者

相关

在下列比赛中:

2019.1.28作业 & 补题通道