18182: 打怪兽

implementation, sortings, hash table, http://cs101.openjudge.cn/practice/18182/

Q神无聊的时候经常打怪兽。现在有一只怪兽血量是b，Q神在一些时刻可以选择一些技能打怪兽，每次释放技能都会让怪兽掉血。现在给出一些技能t~i~,x~i~，代表这个技能可以在ti时刻使用，并且使得怪兽的血量下降x~i~。这个打怪兽游戏有个限制，每一时刻最多可以使用m个技能（一个技能只能用一次）。如果技能使用得当，那么怪兽会在哪一时刻死掉呢？

输入

第一行是数据组数nCases, nCases≤ 100 对于每组数据，第一行是三个整数n,m,b，n代表技能的个数，m代表每一时刻可以使用最多m个技能，b代表怪兽初始的血量。 1≤ n≤ 1000，1≤ m≤ 1000，1≤ b≤ 10^9^ 接下来n行，每一行一个技能t~i~,x~i~，1≤ t~i~≤ 10^9^，1≤ x~i~≤ 10^9^

输出

对于每组数据，输出怪兽在哪一时刻死掉，血量小于等于0就算挂，如果不能杀死怪兽，输出alive

样例输入

样例输出

alive
1

提示：技能不保证按照时刻顺序输入

来源：cs101-2015 期末机考

2020fall-cs101，杨永祥，思路比较简单，时间做 key，技能为 value，然后创建字典，在遍历过程中修改 value中保存的技能伤害就可。

2020fall-cs101，成泽恺。思路：创建字典，将技能的 t~i~ 作为键，x~i~ 作为值存入，x~i~ 存成列表形式，然后每一个回合按时间从前向后遍历字典的值，按 m 判断这一时刻最多能打掉多少血，situation 初始值设为 alive，一旦血量小于等于 0，赋值为这个回合，最后输出 situation。

用了字典，注意字典本身无序，只能对 keys 或 values 排序。

用defaultdict，就不用判断key是否在字典中了。defaultdict会自动为这个键创建一个默认值。

python

from collections import defaultdict

cases = int(input())

for _ in range(cases):
    situation = "alive"
    n, m, b = map(int, input().split())
    a = defaultdict(list)
    
    # Input coordinates
    for _ in range(n):
        x, y = map(int, input().split())
        a[x].append(y)
        
    # Process coordinates
    for x in sorted(a):
        if m >= len(a[x]):
            b -= sum(a[x])
        else:
            a[x].sort(reverse=True)
            b -= sum(a[x][:m])
        if b <= 0:
            situation = x
            break
    
    print(situation)

如果 m 比较大的话，heapq.nlargest 可能会比较慢。可以考虑在收集数据时直接维护一个大小为 m 的堆。

python

# 韩博文，24城市与环境学院
from collections import defaultdict
import heapq

for _ in range(int(input())):
    n, m, b = map(int, input().split())
    d = defaultdict(list)

    # Collect all the damage values for each time point
    for _ in range(n):
        t, x = map(int, input().split())
        d[t].append(x)

    # Calculate the total damage for each time point using a heap
    for t in d:
        if len(d[t]) > m:
            d[t] = sum(heapq.nlargest(m, d[t]))
        else:
            d[t] = sum(d[t])

    # Sort the time points by their occurrence
    dp = sorted(d.items())

    # Apply the damage and check if the blood is depleted
    for t, damage in dp:
        b -= damage
        if b <= 0:
            print(t)
            break
    else:
        print('alive')

在收集数据时直接维护一个大小为 m 的堆，这样可以减少后续的计算开销。如果堆的大小已经达到 m，则使用 heapq.heappushpop 将新值加入堆，并弹出最小值。这样可以确保堆中始终保留最大的 m 个值。

python

# 韩博文，24城市与环境学院
from collections import defaultdict
import heapq

for _ in range(int(input())):
    n, m, b = map(int, input().split())
    d = defaultdict(list)

    # Collect all the damage values for each time point and maintain a heap of size m
    for _ in range(n):
        t, x = map(int, input().split())
        if len(d[t]) < m:
            heapq.heappush(d[t], x)
        else:
            heapq.heappushpop(d[t], x)

    # Calculate the total damage for each time point
    for t in d:
        d[t] = sum(d[t])

    # Sort the time points by their occurrence
    dp = sorted(d.items())

    # Apply the damage and check if the blood is depleted
    for t, damage in dp:
        b -= damage
        if b <= 0:
            print(t)
            break
    else:
        print('alive')

2022fall-cs101，梁天昊。把根据 m 计算每个时间点能造成的最大伤害sum(d[i][:m]) 提到了循环前面，相较题解更简单。

python

for _ in range(int(input())):
    n,m,b = map(int, input().split(' '))
    d = {}
    for i in range(n):
        t,x=map(int, input().split(' '))
        if t not in d.keys():
            d[t] = [x]
        else:
            d[t].append(x)
    for i in d.keys():
        d[i].sort(reverse=True)
        d[i] = sum(d[i][:m])
    dp = sorted(d.items())
    for i in dp:
        b -= i[1]
        if b<=0:
            print(i[0])
            break
    else:
        print('alive')

python

nCases = int(input())
while nCases>0:
        nCases -= 1
        n,m,b = [int(i) for i in input().split()]

        skill = []
        for i in range(n):
                t,x = [int(i) for i in input().split()]
                skill.append( (t, x) )

        sort_skill = sorted(skill, key=lambda a: (a[0], -a[1]))

        if sort_skill[0][1]>=b:
                print(sort_skill[0][0])
                continue

        pre_t = sort_skill[0][0]

        first = True
        cnt = 0
        for e in sort_skill:
                if first:
                        b -= e[1]
                        cnt += 1
                        first = False
                        continue

                if e[0]==pre_t:
                        cnt += 1
                else:
                        cnt = 1
                        pre_t = e[0]
                        
                if cnt>m:
                        continue
                
                if e[1]>=b:
                        print(e[0])
                        break
                else:
                        b -= e[1]
        else:
                print('alive')

18182: 打怪兽 ​

18182: 打怪兽