当前位置：首页 > GESP > 2024年GESP五级武器强化（洛谷B4071）解题代码C++版

2024年GESP五级武器强化（洛谷B4071）解题代码C++版

2个月前 (06-07)

一、题目解读

2024年GESP（青少年软件编程能力等级考试）五级中的“武器强化”（洛谷平台题目编号B4071）是一道典型的算法优化问题。题目要求通过合理分配材料，最小化多件武器的修改总成本。核心难点在于如何高效处理武器适配材料的分配策略，涉及动态规划与贪心算法的结合。

二、解题思路

采用“枚举+贪心”策略：

1. 材料计数与排序预处理：统计每件武器初始适配材料数，并对每件武器的修改花费按升序排序，为后续贪心选择做准备。

2. 关键优化：通过枚举第一件武器最终需要的材料数量k，计算其余武器可贡献的材料，并优先选择修改花费最小的材料进行分配。

3. 备选池机制：无法直接分配时，将剩余材料存入备选池，按需取出，确保总成本最小化。

三、解题步骤

1. 输入与初始化：读取武器数量n和材料总数m，建立材料计数数组cnt和修改花费二维数组cost。

2. 数据预处理：对每件武器的修改花费排序（sort()）。

3. 核心循环：

枚举第一件武器的目标材料数k，计算剩余需求need。

遍历其他武器，优先分配最便宜的修改材料，若材料不足则存入备选池。

对备选池排序后补充剩余需求，更新总成本。

4. 结果输出：取所有枚举情况中的最小总成本。

四、代码与注释

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

int main() {
    int n, m;
    cin >> n >> m; // 输入武器数量和材料总数
    
    vector<int> cnt(n+1, 0); // 各武器适配材料计数
    vector<vector<int>> cost(n+1); // 各武器修改花费
    
    // 读取输入数据
    for (int i = 0; i < m; i++) {
        int p, c;
        cin >> p >> c; // 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;
        int need = k - cnt[1];
        vector<int> pool;
        
        // 处理其他武器
        for (int i = 2; i <= n; i++) {
            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;
}