CF1592A Gamer Hemose
题目描述
有一天,Ahmed\_Hossam 去找 Hemose,说:“我们来做一道 gym 题吧!”Hemose 不想做题,因为他正在玩 Valorant,于是他想了一个问题来分散 Ahmed 的注意力。不幸的是,Ahmed 解不出来……你能帮帮他吗?
在 Valorant 游戏中,有一个特工拥有 $n$ 把武器。第 $i$ 把武器的伤害值为 $a_i$,特工将要面对一个生命值为 $H$ 的敌人。
特工会进行一次或多次攻击,直到敌人死亡。
每次攻击时,他可以选择一把武器,将敌人的生命值减少该武器的伤害值。当敌人的生命值小于等于 $0$ 时,敌人就会死亡。然而,并不是所有事情都那么简单:特工不能连续两次选择同一把武器。
请你求出,特工最少需要攻击多少次才能杀死敌人。
输入格式
每组测试数据包含多个测试用例。第一行包含一个整数 $t$ $(1 \leq t \leq 10^5)$,表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 $n$ 和 $H$ $(2 \leq n \leq 10^3, 1 \leq H \leq 10^9)$,分别表示可用武器的数量和敌人的初始生命值。
每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^9)$,表示每把武器的伤害值。
保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。
输出格式
对于每个测试用例,输出一个整数,表示特工最少需要攻击多少次才能杀死敌人。
说明/提示
在第一个测试用例中,特工可以使用第二把武器,使敌人的生命值变为 $4-7=-3$。$-3 \le 0$,所以敌人死亡,只需要攻击 $1$ 次。
在第二个测试用例中,特工可以先用第一把武器,再用第二把武器。此时敌人的生命值变为 $6-4-2=0$,也就是说攻击 $2$ 次即可杀死敌人。
在第三个测试用例中,特工可以依次使用第三把、第一把、第三把武器,使敌人的生命值变为 $11-7-2-7=-5$,共攻击 $3$ 次。注意不能连续两次使用第三把武器,即使 $11-7-7