文章目录
- 题目描述
- 输入格式
- 输出格式
- 样例
- 样例输入
- 样例输出
- 数据范围与提示
- 思路与部分实现
- 完整代码
题目描述
在游戏 Minecraft 中，玩家可以通过种树来使木材再生。玩家需要将树苗种在泥土上，然后等待它长成大树，期间可以利用骨粉来催熟树苗。
Steve 种了 n n n 棵树苗，自然状态下第 i i i 棵树苗长成大树需要的时间为 t i t_i ti 分钟。由于骨粉不容易获取，Steve 每分钟至多只会用 1 1 1 瓶骨粉。每瓶骨粉可以使一棵树苗的剩余生长时间减少 k k k 分钟。如果该树苗的剩余生长时间 ≤ k \leq k ≤k，那么它会立刻长成大树。
合理规划骨粉的使用，可以使所有树苗长成大树所需的时间减少。求：最少需要等待多少分钟，所有的树苗都能长成大树？
输入格式
第一行是一个正整数 n n n；
第二行是 n n n 个正整数，表示自然状态下各个树苗成熟需要的时间 t i t_i ti；
第三行是一个非负整数 k k k。
输出格式
一个正整数，最少需要等待的分钟数。
样例
样例输入
3
2 3 9
5
样例输出
3
数据范围与提示
时间限制 1s \text{1s} 1s，空间限制 64MB \text{64MB} 64MB。
共 10 10 10 组测试数据，所有数据均满足 0 ≤ k ≤ 1 0 5 0 \leq k \leq 10^5 0≤k≤105。
测试点 # 1 1 1 ~ # 2 2 2： n ≤ 10 n \leq 10 n≤10， t i ≤ 20 t_i \leq 20 ti≤20
测试点 # 3 3 3 ~ # 4 4 4： n ≤ 1000 n \leq 1000 n≤1000， t i ≤ 2000 t_i \leq 2000 ti≤2000
测试点 # 5 5 5 ~ # 6 6 6： n ≤ 1 0 5 n \leq 10^5 n≤105， t i ≤ 2 × 1 0 5 t_i \leq 2 \times 10^5 ti≤2×105
测试点 # 7 7 7 ~ # 10 10 10： n ≤ 1 0 5 n \leq 10^5 n≤105， t i ≤ 1 0 9 t_i \leq 10^9 ti≤109
思路与部分实现
完整代码
