2024年GESP五级真题：贪心算法在游戏强化系统中的应用

一、问题背景分析

题目要求计算将武器1强化到最高等级的最小花费，规则如下：

1. 每种武器有若干适配材料

2. 可以花费金币修改材料适配的武器类型

3. 武器1的适配材料数量必须严格多于其他武器

二、算法设计思路

1. ‌数据预处理‌：统计各武器原始适配材料数量

2. ‌排序优化‌：将修改费用按升序排列

3. ‌枚举策略‌：尝试武器1可能达到的各种材料数量

4. ‌贪心选择‌：每次优先选择修改费用最小的方案

三、完整代码解析（带详细注释）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m; // n种武器，m个材料
    cin >> n >> m;
    
    // cnt[i]表示武器i初始适配材料数量
    vector<int> cnt(n+1, 0); 
    // cost[i]存储修改武器i材料的花费列表
    vector<vector<int>> cost(n+1); 
    
    // 读取输入数据
    for (int i = 0; i < m; i++) {
        int p, c; // 材料适配武器p，修改花费c
        cin >> p >> c;
        cnt[p]++;
        cost[p].push_back(c);
    }
    
    // 对每个武器的修改花费排序（升序）
    for (int i = 1; i <= n; i++) {
        sort(cost[i].begin(), cost[i].end());
    }
    
    long long res = 1e18; // 初始化为极大值
    
    // 枚举武器1可能达到的材料数量k
    for (int k = max(1, cnt[1]); k <= m; k++) {
        long long sum = 0; // 当前k值下的总花费
        int need = k - cnt[1]; // 还需获得的材料数
        vector<int> pool; // 备选修改方案池
        
        // 处理其他武器(2~n)
        for (int i = 2; i <= n; i++) {
            // 最多可以保留(k-1)个不改动
            int can_take = max(0, cnt[i] - (k - 1));
            // 贪心选择：取修改花费最小的can_take个
            for (int j = 0; j < can_take; j++) {
                sum += cost[i][j];
                need--;
            }
            // 剩余材料放入备选池
            for (int j = can_take; j < cost[i].size(); j++) {
                pool.push_back(cost[i][j]);
            }
        }
        
        // 如果还需要更多材料
        if (need > 0) {
            if (pool.size() < need) continue; // 无法满足条件
            sort(pool.begin(), pool.end()); // 再次排序
            for (int i = 0; i < need; i++) {
                sum += pool[i]; // 选择最便宜的方案
            }
        }
        
        res = min(res, sum); // 更新最小值
    }
    
    cout << res << endl;
    return 0;
}

四、关键知识点

1. ‌贪心算法‌：每次选择局部最优解

2. ‌枚举策略‌：遍历所有可能性确保找到全局最优

3. ‌数据预处理‌：排序优化加速后续处理

4. ‌边界处理‌：need变量的动态调整

五、性能优化要点

1. 提前排序避免重复计算

2. 使用vector减少内存分配开销

3. 及时终止不可能的情况(continue)

4. 合理选择数据结构(pool)

六、扩展思考

1. 如果修改花费有上限如何处理？

2. 如何记录具体的修改方案？

3. 如果材料有不同类型限制怎么改进算法？

参考：GESP五级题武器强化