首页 > 试题广场 >

消灭怪物

[编程题]消灭怪物

热度指数：1805 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

现在有一个打怪类型的游戏，这个游戏是这样的，你有 $n$ 个技能，每一个技能会有一个伤害，同时若怪物低于一定的血量，则该技能可能造成双倍伤害，每一个技能最多只能释放一次，已知怪物有 $m$ 点血量，现在想问你最少用几个技能能消灭掉他（血量小于等于 $0$ ）。

输入描述:

第一行输入一个整数 $T$ ，代表有 $T$ 组测试数据。

对于每一组测试数据，一行输入 $2$ 个整数 $n$ 和 $m$ ，代表有 $n$ 个技能，怪物有 $m$ 点血量。

接下来 $n$ 行，每一行输入两个数 $A$ 和 $x$ ，代表该技能造成的伤害和怪物血量小于等于 $x$ 的时候该技能会造成双倍伤害

$1\le T\le 100$
$1\le n\le 10$
$0\le m\le 10^6$
$1\le A,x\le m$

输出描述:

对于每一组数据，输出一行，代表使用的最少技能数量，若无法消灭输出-1。

示例1

输入

输出

3
2
-1

说明

总共3组数据
对于第一组：我们首先用技能1，此时怪物血量剩余90，然后使用技能3，此时怪物剩余血量为85，最后用技能2，由于技能2在怪物血量小于89的时候双倍伤害，故此时怪物已经消灭，答案为3
对于第二组：我们首先用技能1，此时怪物血量剩余90，然后用技能2，由于技能2在怪物血量小于90的时候双倍伤害，故此时怪物已经消灭，答案为2
对于第三组：我们首先用技能1，此时怪物血量剩余90，然后使用技能3，此时怪物剩余血量为85，最后用技能2，由于技能2在怪物血量小于84的时候双倍伤害，故此时怪物无法消灭，输出-1

算法知识视频讲解