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

发表于 2025/11/20

作者 OneCoder

次浏览 13 分钟阅读

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

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

题目要求

题目描述

小杨有 $n$ 种武器和 $m$ 种强化材料。第 $i$ 种强化材料会适配第 $p_i$ 种武器，小杨可以花费 $c_i$ 金币将该材料对应的适配武器修改为任意武器。
小杨最喜欢第 $1$ 种武器，因此他希望适配该武器的强化材料种类数严格大于其他的武器，请你帮小杨计算为了满足该条件最少需要花费多少金币。

输入格式

第一行包含两个正整数 $n,m$，含义如题面所示。
之后 $m$ 行，每行包含两个正整数 $p_i,c_i$，代表第 $i$ 种强化材料的适配武器和修改花费。

输出格式

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

输入输出样例 #1

输入 #1

输出 #1

1

说明/提示

样例解释

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

数据范围

对于 $100\%$ 的数据，保证 $1\le n,m\le 1\, 000$，$1\le p_i\le n$，$1\le c_i\le 10^9$。

子任务编号	得分占比	$n$	$m$
$1$	$20\%$	$\le 2$	$\le 1\, 000$
$2$	$20\%$	$\le 1\,000$	$\le 2$
$3$	$60\%$	$\le 1\, 000$	$\le 1\, 000$

题目分析

解题思路

解题思路

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

这是一个典型的枚举 + 贪心问题。由于 $m$ 的范围较小（$m \le 1000$），我们可以枚举第 $1$ 种武器最终拥有的强化材料数量 $x$。$x$ 的可能的取值范围是第 $1$ 种武器初始拥有的材料数量到总材料数 $m$。

对于一个确定的目标数量 $x$：

条件 1：第 $1$ 种武器的数量必须达到 $x$。
条件 2：其他所有武器的材料数量必须严格小于 $x$（即最多 $x-1$）。

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

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

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

算法步骤
1. 读取输入，$n$ 和 $m$。
2. 统计第 $1$ 种武器的初始材料数量 cnt1。
3. 将其他武器（$2 \sim n$）对应的材料修改花费存入各自的列表 materials[p] 中，并对每个列表从小到大排序，以便后续贪心选取。
4. 枚举第 $1$ 种武器的最终数量 $i$（从 cnt1 循环到 $m$）：
  - 初始化当前花费 cur_cost = 0，当前需要额外移动到第 $1$ 种武器的材料数 total_movecount = 0。
  - 创建一个备选池 pool，用于存储那些“非强制修改”的材料花费。
  - 遍历其他每种武器 $j$（$2 \sim n$）：
    - 计算武器 $j$ 需要移除的材料数量 move = materials[j].size() - (i - 1)。
    - 如果 move > 0，则将 materials[j] 中前 move 个最小花费累加到 cur_cost，计数 total_movecount 加 move。剩下的元素放入 pool。
    - 如果 move <= 0，则将 materials[j] 中所有元素都放入 pool。
  - 检查第 $1$ 种武器当前数量 cnt1 + total_movecount 是否达到 $i$。
  - 如果未达到，计算缺口 need = i - (cnt1 + total_movecount)。对 pool 进行排序，选取前 need 个最小花费累加到 cur_cost。
  - 更新全局最小花费 total_cost。
5. 输出 total_cost。
复杂度
- 时间复杂度：外层循环枚举 $i$ 最多 $m$ 次。内层循环遍历武器 $O(n)$，收集 pool 元素 $O(m)$，对 pool 排序 $O(m \log m)$。总时间复杂度约为 $O(m \cdot (n + m \log m))$。在 $n, m \le 1000$ 的数据范围内，计算量约为 $10^7$ 级别，可以通过。
- 空间复杂度：需要存储所有材料的花费，空间复杂度为 $O(m)$。

示例代码

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

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP 学习专题站：GESP WIKI
“luogu-”系列题目可在洛谷题库进行在线评测。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号

GESP, 五级

本文由作者按照 CC BY-NC-SA 4.0 进行授权