首页 > 试题广场 >

消灭怪物

[编程题]消灭怪物

热度指数：1591 时间限制：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

算法知识视频讲解

Python

怎么还不发offer

python3

#利用回溯解决，但是使用python时容易超时，所以增加了剪枝

t = int(input())
for _ in range(t):
    #n个技能，m点血量
    n,m = list(map(int,input().split()))
    tem = [] #存储每个技能的伤害
    #tem.sort(key=lambda x:(-x[1],-x[0]))
    
    for _ in range(n):
        tem.append(tuple(map(int,input().split())))
    
    length = len(tem)
    ans = -1
    def dfs(blood,visit=set()):
        global ans
        
        #假设剩余技能全部打出二倍伤害
        rest_max_sum = sum([2*tem[i][0] for i in range(length) if i not in visit])
        if blood > rest_max_sum: return #剪枝

        if ans != -1 and len(visit) >= ans: return #剪枝

        if len(visit) == length and blood > 0:
            return 
        if blood <= 0:
            ans = min(ans,len(visit)) if ans >= 0 else len(visit)
        for ind,(x,y) in enumerate(tem):
            if ind not in visit:
                visit.add(ind)
                if blood <= y:
                    dfs(blood-2*x,visit)
                else:
                    dfs(blood-x,visit)
                visit.remove(ind)
    dfs(m)
    print(ans)

编辑于 2023-07-31 21:14:10 回复(0)