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

要解决这个问题，我们需要不断找到当前生命值最高的怪物并对其造成伤害，直到所有怪物死亡。由于怪物的数量可能非常大（最多可达 $3 \times 10^5$），我们需要一个高效的数据结构来快速找到当前生命值最高的怪物。 这里，我们可以使用一个大顶堆（优先队列）来维护怪物的生命值。每次从堆中取出当前生命值最高的怪物，并对其造成伤害。如果伤害后生命值变为非正数，则记录该怪物已死亡，否则将更新后的生命值重新放回堆中。 以下是实现这个算法的 C++ 代码： ```cpp #include <iostream> #include <vector> #include <queue> #include <tuple> using namespace std; int main() { int n, k; cin >> n >> k; // 使用优先队列（大顶堆）存储怪物编号和生命值 priority_queue<pair<long long, int>> pq; vector<long long> monsterHealth(n); for (int i = 0; i < n; ++i) { cin >> monsterHealth[i]; pq.push({monsterHealth[i], i + 1}); // pair 中 first 是生命值，second 是怪物编号 } vector<int> deathOrder; while (!pq.empty()) { auto top = pq.top(); pq.pop(); long long health = top.first; int id = top.second; health -= k; if (health > 0) { pq.push({health, id}); // 如果生命值还大于0，则重新放回堆中 } else { deathOrder.push_back(id); // 否则记录死亡顺序 } } // 输出死亡顺序 for (int id : deathOrder) { cout << id << " "; } return 0; } ``` 逻辑点 1. 使用大顶堆：优先队列（大顶堆）确保每次都能快速找到当前生命值最高的怪物。 2. 处理怪物生命值更新：如果怪物在受到伤害后生命值仍大于0，则更新其生命值并重新放入堆中。 3. 记录死亡顺序：当怪物生命值小于或等于0时，记录其编号到死亡顺序列表中，最后输出该列表。 这样，我们就能高效地确定所有怪物的死亡顺序。 [2025-01-10 09:38:47 | AI写代码神器 | 568点数解答]