题目描述 御坂正在玩一个电脑游戏。他的角色正在杀死一些怪物。有n 个怪物，编号从1−n ，第i 个怪物最初的生命值为ai 。 御坂的角色可以对当前生命值最高的怪物造成k 点伤害。如果其中有几个，则选择编号较小的一个。如果怪物的生命值小于或等于0，在御坂使用他的能力后，它就会死亡。 御坂使用他的能力，直到所有怪物死亡。你的任务是确定怪物死亡的顺序。 输入描述 第一行是怪物的数量n(1≤n≤3×105) 和御坂每次可以对怪物造成的伤害k(1≤k≤109) 。 第二行是每个怪物的生命值ai(1≤ai≤109) 。 输出描述 输出怪物的死亡顺序

为了确定怪物死亡的顺序，我们可以使用一个最大堆（优先队列）来持续跟踪当前生命值最高的怪物。在每次操作中，我们选择当前堆顶元素（即生命值最高的怪物，如果有多个则选择编号最小的），并对其造成伤害。如果该怪物生命值变为非正数，则将其从堆中移除，并记录下其死亡顺序。重复这个过程直到堆为空。 以下是实现这个逻辑的Python代码： ```python import heapq def monster_death_order(n, k, health_values): # 使用负值来表示堆，因为Python的heapq是最小堆，这样负值最大的（即原始值最大的）会在堆顶 # 同时存储怪物的编号和生命值，以处理生命值相同时编号较小者优先的情况 max_heap = [(-health, i + 1) for i, health in enumerate(health_values)] heapq.heapify(max_heap) death_order = [] while max_heap: # 取出当前生命值最高的怪物（注意取负值是为了在最小堆中模拟最大堆） health, monster_id = heapq.heappop(max_heap) health = -health # 恢复为正值 # 对怪物造成伤害 health -= k # 如果怪物生命值小于等于0，记录其死亡顺序 if health <= 0: death_order.append(monster_id) else: # 如果怪物未死亡，则重新放入堆中 heapq.heappush(max_heap, (-health, monster_id)) return death_order # 输入部分 n, k = map(int, input().split()) health_values = list(map(int, input().split())) # 调用函数并输出结果 print(" ".join(map(str, monster_death_order(n, k, health_values)))) ``` 逻辑点需要注意： 1. 使用负值处理最大堆：由于Python的`heapq`库默认实现的是最小堆，我们通过存储负值来模拟最大堆的行为。 2. 处理多个最高生命值的情况：在堆中，如果两个怪物的生命值相同，由于我们同时存储了怪物的编号，编号较小的怪物会先被弹出（因为Python的`tuple`比较是按元素顺序进行的）。 3. 性能优化：使用堆数据结构可以确保每次取出和插入操作的时间复杂度都是O(log n)，这对于处理多达300,000个怪物来说是高效的。 [2025-01-10 09:37:59 | AI写代码神器 | 574点数解答]