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

要解决这个问题，我们需要不断地找到当前生命值最高的怪物并对其造成伤害，直到所有怪物死亡。为了高效地找到当前生命值最高的怪物，可以使用优先队列（最大堆）。 以下是实现该算法的C++代码： ```cpp #include <iostream> #include <vector> #include <queue> #include <tuple> using namespace std; int main() { int n, k; cin >> n >> k; // 存储怪物生命值和其编号的pair priority_queue<pair<long long, int>> pq; vector<long long> monsterHealth(n); for (int i = 0; i < n; ++i) { cin >> monsterHealth[i]; pq.emplace(monsterHealth[i], i + 1); // 使用pair<生命值, 编号>存入优先队列 } vector<int> deathOrder; while (!pq.empty()) { auto [hp, id] = pq.top(); pq.pop(); hp -= k; if (hp > 0) { pq.emplace(hp, id); // 如果怪物还没死，重新放入队列 } else { deathOrder.push_back(id); // 记录死亡顺序 } } // 输出死亡顺序 for (int id : deathOrder) { cout << id << " "; } return 0; } ``` 代码说明： 1. 输入读取：首先读取怪物数量 `n` 和每次伤害 `k`，然后读取每个怪物的生命值。 2. 优先队列：使用 `priority_queue<pair<long long, int>>` 来存储怪物的生命值和编号，其中 `long long` 用于存储生命值以防止溢出，`int` 用于存储怪物编号。 3. 处理过程： - 每次从优先队列中取出当前生命值最高的怪物。 - 对其造成伤害 `k`。 - 如果怪物生命值大于 0，则重新将其放入优先队列。 - 否则，记录其编号到死亡顺序中。 4. 输出结果：按怪物死亡顺序输出编号。 额外需要注意的逻辑点： 1. 数据类型选择：由于生命值和伤害可能非常大，选择 `long long` 类型来存储生命值以防止溢出。 2. 优先队列的使用：优先队列（最大堆）确保每次都能高效地找到当前生命值最高的怪物。 3. 边界条件：输入值应在题目给定的范围内，确保代码在处理边界情况时不会出错。 [2025-01-10 09:29:46 | AI写代码神器 | 600点数解答]