【GESP】C++ 三级真题解析，[2025年12月，第十二次认证]第二题小杨的智慧购物

GESP C++ 2025年12月，三级真题第二题，考察一维数组考点，比第一题难度还是有提升的。题目难度⭐⭐☆☆☆。

第二题，小杨的智慧购物

题目要求

题目描述

---

题目分析

1. 核心逻辑

本题的核心任务是从大量商品信息中筛选出每种文具的最低价格，并计算购买所有 $M$ 种文具的总花费。

关键要素：

1. 文具种类：共有 $M$ 种不同的文具。
2. 选择策略：对于第 $k$ 种文具，如果商店里有多件，我们只选择最便宜的那一件。
3. 计算目标：总花费 = 第 1 种文具的最低价 + 第 2 种文具的最低价 + … + 第 $M$ 种文具的最低价。

2. 解题思路

这就好比你去超市买 $M$ 样不同的东西，每样东西可能有好几个品牌或者不同价格的包装。为了省钱，你会把每样东西都看一遍，记下每样东西见过的最低价格，最后把这些最低价格加起来就是你要花的钱。

具体算法步骤如下：

1. 初始化价格记录表：

我们需要一个“记账本”来记录每种文具的最低价格。可以使用一个数组（或 vector）min_prices，大小设为 $M+1$（方便直接用下标 $1 \dots M$ 对应文具种类）。

初始时，我们要把每种文具的价格设为一个无穷大的数（例如 1000000000）。这表示还在还没看到这种文具，或者假设它的价格非常高，这样第一次遇到真实价格时肯定能更新。

1. 遍历所有商品：

依次检查商店里的 $N$ 件商品，对于每件商品：

• 读取它的种类 $k$ 和价格 $p$。
  • 比较：当前价格 $p$ 是否比我们“记账本”上记录的第 $k$ 种文具的最低价格 min_prices[k] 还要低？
  • 更新：如果 $p$ 更低，就划掉原来的价格，把 min_prices[k] 更新为 $p$。

1. 计算总和：

遍历完成后，“记账本”上 min_prices[1] 到 min_prices[M] 存储的就是每种文具的最终最低价。将它们累加起来即可得到答案。

3. 复杂度分析

• 时间复杂度：我们只需要遍历一遍输入的 $N$ 件商品，每次操作都是简单的比较和赋值，所以时间复杂度是 $O(N)$。这非常高效，可以通过本题的数据规模。
• 空间复杂度：我们需要一个长度为 $M$ 的数组来存储价格，所以空间复杂度是 $O(M)$。

---

示例代码

#include <algorithm>
#include <iostream>
#include <vector>

/**
 * GESP 2025年12月 三级编程题 T2: 小杨的智慧购物
 *
 * 题目核心：
 * 1. 小杨需要购买 M 种文具。
 * 2. 商店里共有 N 件文具，每件都有种类 K 和价格 P。
 * 3. 策略：对于每种文具，只购买最便宜的那一件。
 * 4. 目标：计算买齐这 M 种文具需要的最小总花费。
 *
 * 算法思路：
 * 1. 使用一个数组（或 vector） min_prices 来记录每种文具当前发现的最低价格。
 *    数组大小设为 M +
 * 1，初始值设为一个很大的数（无穷大），表示尚未找到该类文具。
 * 2. 遍历输入的 N 件文具：
 *    - 读取当前文具的种类 k 和价格 p。
 *    - 尝试更新第 k 种文具的最低价格：min_prices[k] = min(min_prices[k], p)。
 * 3. 遍历完所有文具后，将 1 到 M 种文具的最低价格累加，即为结果。
 */

const int INF = 1000000000;  // 定义无穷大

int main() {
    int m, n;
    // 读取种类数 M 和总文具数 N
    std::cin >> m >> n;

    // 创建 min_prices 数组，大小为 M + 1，初始化为 INF
    // 下标 1 代表第 1 种文具，依此类推
    std::vector<int> min_prices(m + 1, INF);

    for (int i = 0; i < n; i++) {
        int k, p;
        // 读取每件文具的种类和价格
        std::cin >> k >> p;

        // 如果当前这件文具的价格比之前记录的第 k 种文具的最低价还低，则更新
        if (p < min_prices[k]) {
            min_prices[k] = p;
        }
    }

    int total_cost = 0;
    // 累加所有种类文具的最低价格
    for (int i = 1; i <= m; i++) {
        total_cost += min_prices[i];
    }

    // 输出总花费
    std::cout << total_cost << std::endl;

    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 认证学习微信公众号