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

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

3个月前 (06-07)

2024年GESP五级武器强化(洛谷B4071)解题代码C++版 GESP五级 武器强化  动态规划 第1张

一、题目解读

    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;
}

五、总结

该解法利用排序与贪心思想,通过枚举关键变量(第一件武器的目标材料数)来降低时间复杂度。核心优化点在于:

    1. 预处理排序减少后续选择复杂度;

    2. 备选池动态调整确保材料分配的最优性;

    3. 枚举范围限制在合理区间,避免无效计算。

此思路对同类资源分配问题具有通用性,适合算法竞赛与编程能力提升学习。



原创内容 转载请注明出处

分享给朋友:

相关文章

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

力扣1137题:动态规划解泰波那契数 高效求解第N项的秘密

一:重新解读题目泰波那契数列是一个充满数学趣味的递推序列:从第3项开始,每个数均为前三个数的和(即Tₙ₊₃ = Tₙ + Tₙ₊₁ + Tₙ₊₂)。当给定整数n时,需要高效计算出第n项的值。面对此类递...

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

CSP-J 2019纪念品题解(洛谷P5662):动态规划+完全背包问题的实战应用

一、题目解读2019年CSP-J的“纪念品”问题(对应洛谷P5662)要求玩家在T天内通过买卖纪念品最大化金币收益。每天可交易N种商品,需计算最优策略下的最终金币数。题目强调动态规划思维与资源分配优化...

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

2024蓝桥杯省赛B组“传送阵”题解(C++代码+图论算法优化)

一、题目解读2024年蓝桥杯省B组“传送阵”题目要求处理一个包含n个节点的图,节点间存在单向传输关系。每个节点i可传送至a[i]指定的节点,形成可能存在的环结构。题目需求解从任意节点出发能到达的最长路...

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

一、题目解读LeetCode 120题“三角形最小路径和”要求给定一个由数字组成的三角形,从顶部开始向下移动,每次可向左或向右移动一格,计算从顶至底的最小路径和。三角形以二维向量形式给出,每层元素数量...

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。