怪物死亡顺序计算的C语言实现

回答：

要解决这个问题，我们可以使用一个优先队列（最大堆）来管理怪物的血量和编号。每次我们从堆中取出血量最高的怪物进行攻击，直到所有怪物都死亡。以下是用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int health;
    int index;
} Monster;

// 比较函数，用于最大堆
int compare(const void *a, const void *b) {
    Monster *monsterA = (Monster *)a;
    Monster *monsterB = (Monster *)b;
    if (monsterA->health == monsterB->health) {
        return monsterA->index - monsterB->index; // 编号小的优先
    }
    return monsterB->health - monsterA->health; // 血量高的优先
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    
    Monster monsters[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &monsters[i].health);
        monsters[i].index = i + 1; // 编号从1开始
    }

    // 使用qsort进行排序，模拟最大堆的行为
    qsort(monsters, n, sizeof(Monster), compare);

    int deathOrder[n];
    int deathCount = 0;

    while (deathCount < n) {
        // 取出血量最高的怪物
        Monster *current = &monsters[0];

        // 计算当前怪物的剩余血量
        current->health -= k;

        if (current->health <= 0) {
            // 记录死亡顺序
            deathOrder[deathCount++] = current->index;

            // 将当前怪物的血量设为一个负值，表示已死亡
            current->health = -1;

            // 重新排序
            qsort(monsters, n, sizeof(Monster), compare);
        }
    }

    // 输出死亡顺序
    for (int i = 0; i < n; i++) {
        printf("%d ", deathOrder[i]);
    }
    printf("\n");

    return 0;
}

代码说明：

结构体定义：定义了一个 Monster 结构体来存储怪物的血量和编号。
比较函数：compare 函数用于 qsort，根据血量和编号对怪物进行排序。
输入处理：读取怪物数量 n 和攻击力 k，然后读取每个怪物的血量。
主循环：在每次循环中，取出血量最高的怪物，减少其血量。如果血量小于等于零，则记录其编号，并将其血量设为负值以表示死亡。然后重新排序。
输出结果：最后输出所有怪物的死亡顺序。

注意事项：

由于使用了 qsort，每次攻击后都需要重新排序，这在性能上可能不是最优的，但对于题目给定的约束条件（n ≤ 100000），这个实现是可行的。
代码中使用了 qsort 来模拟最大堆的行为，实际应用中可以考虑使用更高效的堆结构来优化性能。

怪物死亡顺序计算的C语言实现

由 ChatGPT4o 使用 ChatGPT 4o 回答

代码说明：

注意事项：