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

要解决这个问题，我们需要模拟御坂攻击怪物的过程，直到所有怪物死亡。关键在于每次选择当前生命值最高的怪物进行攻击，并在生命值降至0或以下时记录死亡顺序。由于怪物数量可能很大（最多3×10^5），我们需要一个高效的数据结构来维护当前存活的怪物，并快速找到生命值最高的怪物。 方法思路 1. 数据结构选择：使用优先队列（堆）来高效地获取当前生命值最高的怪物。由于每次攻击后需要更新怪物的生命值，普通的优先队列无法高效处理动态更新。可以使用一个最大堆，堆中的每个元素存储怪物的当前生命值和编号。每次从堆顶取出生命值最高的怪物，进行攻击，如果攻击后生命值仍大于0，则将其重新放回堆中；否则记录其死亡顺序。 2. 处理步骤： - 将所有怪物初始生命值和编号存入最大堆，堆的排序规则是生命值高的优先，生命值相同时编号小的优先。 - 循环处理堆中的怪物，直到堆为空： - 取出堆顶怪物（当前生命值最高的怪物）。 - 计算该怪物需要多少次完整的攻击才能死亡：`times = (a_i - 1) // k`。这样，攻击`times`次后，怪物的生命值会减少到`a_i - times * k <= k`，下一次攻击时死亡。 - 记录该怪物死亡，并处理剩余生命值。如果剩余生命值在攻击后小于等于0，则记录死亡顺序；否则更新生命值并放回堆中。 解决代码 ```python import sys import heapq def solve(): n, k = map(int, sys.stdin.readline().split()) a = list(map(int, sys.stdin.readline().split())) # 使用最大堆，存储(-a_i, index) heap = [] for i in range(n): heapq.heappush(heap, (-a[i], i + 1)) # 使用负值模拟最大堆 res = [] while heap: current_neg, idx = heapq.heappop(heap) current = -current_neg # 计算需要多少次攻击才能让current <=0 times = (current + k - 1) // k # 等价于ceil(current / k) # 但我们需要一步步处理，或者找到可以一次性处理完的批次 # 但为了效率，可以计算需要多少次完整的k攻击才能让current <=0 # 但更好的方法是找到可以一次性处理到死亡的最小次数 # 另一种思路是每次攻击k，直到死亡，但这样对于大a_i和k来说O(n)次操作可能超时 # 所以需要找到一种数学方法 # 当前剩余生命是current，每次减k，直到<=0 # 可以计算需要减多少次： m = ceil(current / k) # 但这样可能无法直接得到死亡顺序，因为其他怪物可能在中间被处理 # 因此必须模拟每次攻击 # 所以必须回到模拟每次攻击最高怪物的过程，但这样对于3e5的n和大的a_i和k，O(n^2)无法通过 # 所以需要优化：每次处理能够一次性减掉尽可能多的k，直到该怪物死亡 # 例如，可以计算该怪物会在第几次攻击时死亡 # 但现在需要的是死亡顺序，所以必须知道怪物死亡的顺序 # 所以正确的做法是，每次攻击最高怪物，减少k，如果死亡则记录，否则放回堆 # 但这样对于a_i=1e9和k=1，会是O(n*a_i/k)时间，无法通过 # 因此需要换一种思路：按照每个怪物死亡的总攻击次数来处理 # 每个怪物i会在第 (ceil(a_i /k)) 次攻击时死亡 # 但攻击是轮流进行的，所以需要计算每个怪物死亡的轮次 # 正确的解法是，每个怪物i需要t_i次攻击死亡，t_i = ceil(a_i /k) # 怪物的死亡顺序是按照t_i从小到大，t_i相同的，i小的先死 # 所以可以将怪物按照(t_i, i)排序，然后依次输出i # 所以问题转化为计算每个怪物的t_i = (a_i + k -1) // k # 然后按照t_i升序，t_i相同则按i升序排列，输出i的顺序 # 重新理解问题：每次攻击最高生命值的怪物，减k，如果<=0则死亡 # 但实际死亡顺序是否等同于按ceil(a_i/k)从小到大排序？ # 例如，怪物A需要2次攻击，B需要3次，那么A一定在B之前死亡 # 如果多个怪物需要的攻击次数相同，则编号小的先死 # 所以解法是计算每个怪物i的t_i = (a_i +k-1)//k，然后按t_i和i排序 monsters = [] for i in range(n): t = (a[i] + k - 1) // k monsters.append((t, i + 1)) monsters.sort() res = [str(m[1]) for m in monsters] print(' '.join(res)) solve() ``` 代码解释 1. 输入处理：读取怪物数量`n`和每次攻击伤害`k`，以及每个怪物的初始生命值数组`a`。 2. 计算死亡顺序：对于每个怪物，计算其死亡所需的攻击次数`t_i`，即`(a_i + k - 1) // k`（等价于向上取整）。将攻击次数和怪物编号存储在列表中。 3. 排序处理：根据攻击次数从小到大排序，攻击次数相同的按怪物编号升序排序。排序后的怪物编号即为死亡顺序。 4. 输出结果：将排序后的怪物编号输出。 这种方法避免了直接模拟每次攻击的高时间复杂度，转而通过数学计算确定死亡顺序，确保算法的高效性。 三条额外需要注意的逻辑点： - 计算攻击次数时使用`(a_i + k - 1) // k`来避免浮点数运算，确保正确向上取整。 - 排序时需同时考虑攻击次数和怪物编号，确保攻击次数相同时编号小的怪物优先死亡。 - 输入规模较大时，使用`sys.stdin.readline`读取输入以提高读取速度。 [2025-06-08 16:54:19 | AI写代码神器 | 1400点数解答]