OneCoder Avatar
OneCodercoderli.com · 1024 篇博文
五级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++五级真题(贪心思想考点) luogu-B4071 [GESP202412 五级] 武器强化

📅 2025-11-20·✍️ OneCoder·计算中...·⏱️ 13 分钟

GESP C++ 2024年12月五级真题,贪心思想考点,涉及枚举和排序,题目难度⭐⭐⭐☆☆,五级正常难度。洛谷难度等级普及/提高−

luogu-B4071 [GESP202412 五级] 武器强化

题目要求

题目描述

小杨有 种武器和 种强化材料。第 种强化材料会适配第 种武器,小杨可以花费 金币将该材料对应的适配武器修改为任意武器。

小杨最喜欢第 种武器,因此他希望适配该武器的强化材料种类数严格大于其他的武器,请你帮小杨计算为了满足该条件最少需要花费多少金币。

输入格式

第一行包含两个正整数 ,含义如题面所示。

之后 行,每行包含两个正整数 ,代表第 种强化材料的适配武器和修改花费。

输出格式

输出一个整数,代表能够使适配第 种武器的强化材料种类数严格大于其他的武器最少需要花费的金币。

输入输出样例 #1

输入 #1
PLAINTEXT5 行
4 4
1 1
2 1
3 1
3 2
输出 #1
PLAINTEXT1 行
1

说明/提示

样例解释

花费 ,将第三种强化材料的适配武器由 改为 。此时,武器 有 种强化材料适配,武器 和武器 都各有 种强化材料适配,满足适配第 种武器的强化材料种类数严格大于其他的武器。

数据范围

对于 的数据,保证 ,,。

子任务编号 得分占比

题目分析

解题思路

  1. 解题思路

本题的核心目标是让第 种武器的强化材料数量严格大于其他任意一种武器的强化材料数量,即对于任意 ,都有 。同时要求总花费最小。

这是一个典型的枚举 + 贪心问题。 由于 的范围较小(),我们可以枚举第 种武器最终拥有的强化材料数量 。 的可能的取值范围是第 种武器初始拥有的材料数量到总材料数 。

对于一个确定的目标数量 :

  • 条件 1:第 种武器的数量必须达到 。
  • 条件 2:其他所有武器的材料数量必须严格小于 (即最多 )。

为了满足上述条件并使花费最小,我们采取以下贪心策略:

  1. 强制削减: 对于除第 种之外的每种武器,如果其现有的材料数量 ,则必须将其减少到 。为了最小化花费,我们优先移除该武器中修改花费最小的那些材料,并将它们改为第 种武器。记录这部分花费和增加的第 种武器数量。
  2. 补足数量: 经过步骤 1 后,如果第 种武器的数量还不足 个,我们需要从剩下的所有可用材料中(包括之前没被强制移除的材料),挑选花费最小的若干个,将其改为第 种武器,直到数量达到 。

我们枚举 的过程中,计算每种情况下的总花费,取最小值即为答案。

  1. 算法步骤

    1. 读取输入, 和 。
    2. 统计第 种武器的初始材料数量 cnt1。
    3. 将其他武器()对应的材料修改花费存入各自的列表 materials[p] 中,并对每个列表从小到大排序,以便后续贪心选取。
    4. 枚举第 种武器的最终数量 (从 cnt1 循环到 ):
      • 初始化当前花费 cur_cost = 0,当前需要额外移动到第 种武器的材料数 total_movecount = 0。
      • 创建一个备选池 pool,用于存储那些“非强制修改”的材料花费。
      • 遍历其他每种武器 ():
        • 计算武器 需要移除的材料数量 move = materials[j].size() - (i - 1)。
        • 如果 move > 0,则将 materials[j] 中前 move 个最小花费累加到 cur_cost,计数 total_movecount 加 move。剩下的元素放入 pool。
        • 如果 move <= 0,则将 materials[j] 中所有元素都放入 pool。
      • 检查第 种武器当前数量 cnt1 + total_movecount 是否达到 。
      • 如果未达到,计算缺口 need = i - (cnt1 + total_movecount)。对 pool 进行排序,选取前 need 个最小花费累加到 cur_cost。
      • 更新全局最小花费 total_cost。
    5. 输出 total_cost。
  2. 复杂度

    • 时间复杂度:外层循环枚举 最多 次。内层循环遍历武器 ,收集 pool 元素 ,对 pool 排序 。总时间复杂度约为 。在 的数据范围内,计算量约为 级别,可以通过。
    • 空间复杂度:需要存储所有材料的花费,空间复杂度为 。

示例代码

C++82 行
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

int main() {
    // n: 武器种类数, m: 强化材料总数
    int n, m;
    std::cin >> n >> m;

    // materials[p] 存储适配第 p 种武器的各种强化材料的修改代价
    // 使用 vector 存储以便后续排序和处理
    std::vector<std::vector<int>> materials(n + 1);
    int cnt1 = 0; // 记录适配第 1 种武器的初始材料数量

    for (int i = 0; i < m; i++) {
        int p, c;
        std::cin >> p >> c;
        if (p == 1) {
            // 如果已经是第 1 种武器的材料,直接计数,不需要花费
            cnt1++;
        } else {
            // 否则记录修改该材料适配第 1 种武器所需的费用
            materials[p].push_back(c);
        }
    }

    // 对于除第 1 种以外的每种武器,将其材料按修改代价从小到大排序
    // 这样在需要减少该武器的材料数量时,可以优先移除代价最小的
    for (int i = 2; i <= n; i++) {
        std::sort(materials[i].begin(), materials[i].end());
    }

    long long total_cost = LLONG_MAX; // 初始化最小总花费为最大值

    // 枚举第 1 种武器最终拥有的材料数量 i
    // i 的范围:从当前的 cnt1 开始,直到所有材料都归它 (m)
    // 目标是:第 1 种武器有 i 个材料,且其他所有武器的材料数都 < i (即最多 i-1 个)
    for (int i = cnt1; i <= m; i++) {
        std::vector<int> pool; // 备选池:存储那些虽然不需要强制买(为了压低别人票数),但可以用来凑第 1 种武器票数的材料
        int total_movecount = 0; // 记录为了“压制”其他武器而必须修改的材料数量
        long long cur_cost = 0;  // 当前方案的总花费

        // 遍历所有武器(materials 实际上从下标 2 开始有效,0 和 1 为空或已处理)
        for (int j = 0; j < materials.size(); j++) {
            // 计算第 j 种武器需要移除多少个材料才能使其数量严格小于 i
            // 原有数量 size,目标保留数量 <= i-1
            // 需要移除的数量 = size - (i - 1) = size - i + 1
            // 代码逻辑:move = size - i,则移除下标 0 到 move 的元素(共 move + 1 个)
            // 移除后剩余:size - (size - i + 1) = i - 1 个,满足条件
            int move = materials[j].size() - i;

            for (int k = 0; k < materials[j].size(); k++) {
                if (k <= move) {
                    // 必须修改的材料(为了让该武器材料数 < i)
                    cur_cost += materials[j][k];
                    total_movecount++;
                } else {
                    // 不需要强制修改的材料,放入备选池
                    // 如果后面第 1 种武器的数量还不够 i,可以从这里挑便宜的买
                    pool.push_back(materials[j][k]);
                }
            }
        }

        // 统计目前第 1 种武器的材料数:初始 cnt1 + 强制修改的 total_movecount
        // 如果还不到目标数量 i,需要从备选池中补足
        if (cnt1 + total_movecount < i) {
            // 对备选池按代价排序
            std::sort(pool.begin(), pool.end());
            // 贪心选取最便宜的几个补充,直到达到数量 i
            for (int j = 0; j < i - total_movecount - cnt1; j++) {
                cur_cost += pool[j];
            }
        }

        // 更新全局最小花费
        total_cost = std::min(total_cost, cur_cost);
    }
    std::cout << total_cost;
    return 0;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!