【GESP】C++ 四级真题解析，[2025年12月，第十二次认证]第二题优先购买

GESP C++ 2025年12月，四级真题第二题，考察结构体定义与自定义排序算法，涵盖贪心思想。题目难度⭐⭐★☆☆。

第二题，优先购买

题目要求

题目描述

---

题目分析

1. 核心逻辑

本题是一个典型的贪心算法结合自定义排序的问题。 我们需要在有限的预算 $M$ 内，按照特定的优先级规则购买尽可能“好”的商品。

核心在于理解购买的优先级规则（优先级依次递减）：

1. 优先级 $V$：数值越小，优先级越高（第一关键关键字）。
2. 价格 $P$：数值越低，越优先（第二关键关键字，当 $V$ 相同时考虑）。
3. 名称 $S$：字典序越小，越优先（第三关键关键字，前两者都相同时考虑）。

2. 解题思路

我们可以把这个问题想象成在只有 $M$ 元钱的情况下，去抢购特价商品。我们需要先列一个清单，把最值得买的排在最前面。

具体的算法步骤如下：

1. 存储商品信息：

由于每个商品有名字、价格、优先级三个属性，最好定义一个结构体 struct Item 来存储，方便管理和排序。

1. 制定排序规则：

这是解题的关键。我们需要写一个比较函数 cmp，告诉计算机如何判断两个商品 a 和 b 谁更值得买：

• 首先看优先级：如果 a.priority != b.priority，则 return a.priority < b.priority;（小的排前面）。
• 其次看价格：如果 a.price != b.price，则 return a.price < b.price;（便宜的排前面）。
• 最后看名字：return a.name < b.name;（字典序小的排前面）。

1. 排序并购买：

• 使用 std::sort 将所有商品按照步骤 2 的规则排好序。
• 从头开始遍历排序后的商品列表，只要手中的钱 $M$ 还够买当前商品（$M \ge P$），就买下它（扣除预算 $M -= P$），并把它的名字记录到结果列表中。

1. 整理结果：

题目要求输出所有购买商品的名字，并按字典序排列。因此，我们需要对记录下的“已购商品名字列表”再进行一次 std::sort，然后依次输出。

3. 复杂度分析

时间复杂度：

• 第一次排序（按购买策略）：$O(N \log N)$。
• 购买遍历：$O(N)$。
• 第二次排序（按名字输出）：最坏情况下买了 $N$ 个商品，复杂度 $O(N \log N)$。
• 总体时间复杂度：$O(N \log N)$。对于 $N \le 10^5$ 的数据规模，完全可以满足时间限制。

空间复杂度：

• 需要存储 $N$ 个商品的信息，复杂度 $O(N)$。

---

示例代码

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

/**
 * GESP 2025年12月 四级编程题 T2: 优先购买
 *
 * 题目核心：
 * 小 A 有 M 元预算，商店有 N 个商品。
 * 每个商品有：名字 S，价格 P，优先级 V。
 *
 * 购买策略（优先级从高到低）：
 * 1. 优先买优先级最高（V 越小优先级越高）的。
 * 2. 优先级相同时，买价格最低的。
 * 3. 优先级和价格都相同时，买名字字典序最小的。
 *
 * 最终输出：所有购买商品的名字，按字典序排列。
 */

struct Item {
    std::string name;
    int price;
    int priority;
};

// 购买排序规则：优先级 -> 价格 -> 名字
bool compareItems(const Item& a, const Item& b) {
    if (a.priority != b.priority) {
        return a.priority < b.priority;  // V 越小越高
    }
    if (a.price != b.price) {
        return a.price < b.price;  // 价格越低越优先
    }
    return a.name < b.name;  // 字典序越小越优先
}

int main() {
    int m, n;
    // 读取预算 M 和商品数量 N
    std::cin >> m >> n;

    std::vector<Item> items(n);
    for (int i = 0; i < n; i++) {
        std::cin >> items[i].name >> items[i].price >> items[i].priority;
    }

    // 1. 按照购买策略对所有商品进行排序
    std::sort(items.begin(), items.end(), compareItems);

    std::vector<std::string> bought_items;

    // 2. 模拟购买过程
    for (int i = 0; i < n; i++) {
        if (m >= items[i].price) {
            // 买得起就买
            m -= items[i].price;
            bought_items.push_back(items[i].name);
        }
    }

    // 3. 将购买的商品按名字字典序排序
    std::sort(bought_items.begin(), bought_items.end());

    // 4. 输出结果
    for (const auto& name : bought_items) {
        std::cout << name << 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 认证学习微信公众号