在打怪游戏中，有n个怪物，第i个怪物的血量为ai。 玩家有两种攻击方式： 普通攻击，每次普通攻击减少怪物一点血量。 技能攻击，每次使用一次技能可以直接消灭一个怪物。

Question

在打怪游戏中，有n个怪物，第i个怪物的血量为ai。
玩家有两种攻击方式：
普通攻击，每次普通攻击减少怪物一点血量。
技能攻击，每次使用一次技能可以直接消灭一个怪物。
玩家最多只能使用k次技能，现在需要求出消灭所有怪物所需的最少普通攻击次数。

Answer 1

引自免费微信小程序：皆我百晓生

为了找到消灭所有怪物所需的最少普通攻击次数，我们可以采用贪心策略。首先，我们将所有的怪物按照血量从大到小排序。然后，优先使用技能攻击血量最大的怪物，直到技能次数用完。接着，对剩余的怪物，我们只需要进行普通攻击，直到所有怪物都被消灭。

以下是C语言实现这个算法的代码：

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

// 定义结构体表示怪物
typedef struct Monster {
    int health;
} Monster;

// 按照血量降序排序函数
int compareMonsters(const void *a, const void *b) {
    return (*(Monster *)b).health - (*(Monster *)a).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);
    }
    
    // 对怪物按血量降序排序
    qsort(monsters, n, sizeof(Monster), compareMonsters);

    // 使用技能攻击血量最大的怪物
    int total_normal_attacks = 0;
    for (int i = 0; i < k && i < n; ++i) {
        total_normal_attacks += monsters[i].health - 1;
        monsters[i].health = 1; // 假设技能攻击后剩余一滴血，方便计算普通攻击次数
    }

    // 计算剩余怪物的普通攻击次数
    for (int i = k; i < n; ++i) {
        total_normal_attacks += monsters[i].health;
    }

    printf("%d\n", total_normal_attacks);
    
    return 0;
}

这段代码首先读取输入的怪物数量n、技能使用次数k以及每个怪物的血量。然后，它创建了一个名为monsters的结构体数组，并对其进行排序。接下来，根据可用的技能次数，对血量最大的怪物使用技能攻击，同时更新总普通攻击次数。最后，对于没有被技能攻击过的怪物，计算它们需要的普通攻击次数，并累加到总普通攻击次数上。程序最后输出总普通攻击次数。