分数: 400 点
问题陈述
你正在出去散步,突然遇到 N 怪物。每个怪物都有一个参数称为 健康,以及健康 i- 第一个怪物是 h_i 相遇的那一刻。当怪物的生命值下降到以下时,怪物会立即消失 0 或以下。
幸运的是,你是一位熟练的魔法师,能够引起爆炸来伤害怪物。在一次爆炸中,你可以对怪物造成如下伤害:
- 选择一只活着的怪物,并以该怪物为中心引发爆炸。爆炸中心怪物的生命值将减少 A,其他每个怪物的生命值都会减少 B。在这里, A 和 B 是预定参数,并且 A > B 成立。
你至少需要引起多少次爆炸才能消灭所有怪物?
约束
- 所有输入值均为整数。
- 1 ≤ N ≤ 10^5
- 1 ≤ B < A ≤ 10^9
- 1 ≤ h_i ≤ 10^9
输入
输入由标准输入按以下格式给出:
N A B h_1 h_2 : h_N
输出
打印消灭所有怪物所需的最小爆炸次数。
示例输入 1
4 5 3 8 7 4 2
示例输出 1
2
你可以在两次爆炸中消灭所有怪物,如下:
- 首先,以怪物为中心引发爆炸 8 健康。四个怪物的生命值变为 3, 4, 1 和 -1,最后一个怪物消失。
- 其次,以怪物为中心引发爆炸 4 剩余健康状况。剩下的三个怪物的生命值变为 0, -1 和 -2,所有怪物现在都消失了。
示例输入 2
2 10 4 20 20
示例输出 2
4
你需要以每个怪物为中心引发两次爆炸,总共四次。
示例输入 3
5 2 1 900000000 900000000 1000000000 1000000000 1000000000
示例输出 3
800000000