题解：怪兽伤害分配问题

题目分析

题目给定了 n 个怪兽，每个怪兽有两个属性：

• num：怪兽可以攻击的最大等级（表示怪兽需要的伤害值）。
• val：怪兽造成的伤害值。

然后给定了一个可用的防御力值 m，每个防御力值只能够防御一次怪兽的伤害。目标是将防御力值分配给这些怪兽，使得总伤害最小化。每个怪兽只能选择一个防御力值来进行防御，而防御力值只能使用一次。

解题思路

本题是一个典型的贪心问题。要想最小化总伤害，我们应该优先让伤害值大的怪兽得到防御。

具体的解决步骤如下：

1. 输入数据： 每个怪兽有两个属性，num 表示怪兽需要的防御力值，而 val 是怪兽的伤害。我们需要在怪兽的 num 范围内为其分配防御力。

2. 排序： 根据伤害值 val 从大到小排序，这样我们就能先处理伤害大的怪兽，确保伤害大的怪兽尽早得到防御。

3. 贪心分配： 对于每个怪兽，从它能使用的最大防御力值 num 开始，往下寻找可用的防御力。如果找到了空缺的防御力，就将该防御力标记为已用；否则，将该怪兽的伤害加到总伤害中。

4. 最终输出： 输出所有怪兽无法得到防御时的总伤害。

代码分析

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 2005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;
 
// 结构体，保存怪兽的最大防御力要求num和伤害值val
struct str
{
    int num, val;
};
 
str s[500010];  // 存储怪兽的信息
int visit[500010];  // 记录哪些防御力已经被使用
 
// 自定义排序函数：根据怪兽的伤害从大到小排序
int cmp(const str a, const str b)
{
    return a.val > b.val;
}
 
int main()
{
    int i, j, n, m;
    while (scanf("%d%d", &n, &m) && n && m)  // 读取怪兽数量n和可用防御力值m
    {
        memset(visit, 0, sizeof(visit));  // 初始化防御力的使用情况
        for (i = 1; i <= n; i++)  // 输入怪兽的最大防御力要求
            scanf("%d", &s[i].num);
        for (i = 1; i <= n; i++)  // 输入怪兽的伤害值
            scanf("%d", &s[i].val);
        
        // 根据伤害从大到小排序怪兽
        sort(s + 1, s + n + 1, cmp);

        int sum = 0;  // 总伤害值
        for (i = 1; i <= n; i++)  // 遍历每个怪兽
        {
            // 尝试从怪兽要求的最大防御力值num开始向下找
            for (j = s[i].num; j > 0; j--)
            {
                if (!visit[j])  // 如果该防御力没有被使用
                {
                    visit[j] = 1;  // 使用该防御力
                    break;
                }
            }
            // 如果没有找到可用的防御力，累加该怪兽的伤害
            if (j == 0)
                sum += s[i].val;
        }
        printf("%d\n", sum);  // 输出总伤害
    }
    return 0;
}

代码解析

1. 结构体 str： 用来存储怪兽的两个属性：

   • num：怪兽所需的防御力。
   • val：怪兽的伤害。

2. 排序： 使用 sort 函数，按照怪兽的伤害 val 从大到小排序。这样，我们就能优先处理伤害更大的怪兽，确保它们尽早得到防御。

3. 贪心算法：

   • 对每个怪兽，从它要求的最大防御力 num 开始向下寻找可用的防御力。
   • 如果找到一个空闲的防御力，就标记为已用，并跳出循环；否则，累加怪兽的伤害到 sum。

4. 输出： 每次计算完所有怪兽的伤害后，输出总伤害 sum。

复杂度分析

• 时间复杂度：

  • 排序：O(n log n)，其中 n 是怪兽的数量。
  • 遍历每个怪兽并分配防御力：每个怪兽最多需要 O(num) 时间来找到可用的防御力。在最坏情况下，num 等于 n，所以每个怪兽的查找时间为 O(n)。因此总的时间复杂度为 O(n^2)。

• 空间复杂度：

  • 使用了 O(n) 空间来存储怪兽的属性和防御力的使用情况。

总结

这道题的核心是贪心算法，通过先处理伤害大的怪兽，确保伤害最小化。排序和贪心配对方法能有效地解决这个问题。虽然在最坏情况下可能会出现 O(n^2) 的时间复杂度，但对于常见的输入规模，这种解法已经足够高效。