CCF-GESP计算机学会等级考试2025年12月四级C++T2 优先级排序与预算优化策略-编程阁

1. 题目背景与需求分析

这道题来自CCF-GESP 2025年12月四级C++考试的第二题，考察的是在实际预算限制下，如何通过优先级排序算法做出最优购物决策。题目设定非常贴近生活场景：假设你有20元预算，面前有4件不同价格、不同优先级的商品，需要按照特定规则选择购买哪些商品。

我第一眼看到这个题目时，立刻联想到现实生活中的购物决策。比如双十一抢购时，我们常常会遇到"满减优惠券不够用"的情况，这时候就需要根据商品的重要性和价格来做出取舍。这道题正是将这种日常决策抽象成了一个可计算的算法问题。

题目给出的购买策略包含三个层次：

首先看优先级（V值越小优先级越高）
优先级相同再看价格（选便宜的）
前两者都相同最后看商品名字典序

这种多条件排序在实际开发中非常常见，比如电商平台的商品展示排序、任务调度系统的优先级处理等。理解并掌握这种多条件排序的实现方法，对提升编程能力很有帮助。

2. 数据结构设计与实现

2.1 结构体的定义

解决这个问题，我首先考虑如何组织商品数据。在C++中，使用结构体(struct)是最自然的选择：

struct Product { string name; // 商品名 int price; // 价格 int priority; // 优先级（越小越高） };

这里我特意把变量名改得更语义化，比如用name代替题目中的s，用price代替p。虽然题目给的变量名很短，但在实际开发中，使用有意义的变量名能让代码更易读、更易维护。

结构体的大小设计也需要注意。题目说明N≤1000，所以我定义数组时可以这样：

Product products[1005]; // 多留5个位置防止越界

2.2 输入处理技巧

读取输入数据时，有几个细节需要注意：

int budget, itemCount; cin >> budget >> itemCount; for(int i = 0; i < itemCount; i++) { cin >> products[i].name >> products[i].price >> products[i].priority; }

这里我习惯从0开始计数，而不是题目示例中的1。虽然两种方式都可以，但从0开始更符合C++数组的标准用法。在实际考试中，要注意题目要求，避免因为下标问题导致错误。

3. 核心算法：多条件排序

3.1 自定义比较函数

这道题的核心在于如何实现题目要求的三层排序规则。在C++中，我们可以通过自定义比较函数来实现：

bool compareProducts(const Product& a, const Product& b) { // 第一优先级：priority越小越靠前 if(a.priority != b.priority) { return a.priority < b.priority; } // 第二优先级：价格低的靠前 if(a.price != b.price) { return a.price < b.price; } // 第三优先级：按字典序排序 return a.name < b.name; }

这个比较函数会被STL的sort函数调用，决定元素的排列顺序。我在这里使用了const引用传参，这是比较函数的推荐写法，可以避免不必要的拷贝。

3.2 排序的实现

有了比较函数，排序就很简单了：

sort(products, products + itemCount, compareProducts);

这里要注意sort的第二个参数是"结束位置"，所以是products + itemCount而不是products + itemCount - 1。这个细节在考试时很容易出错，建议多练习几次。

4. 购买逻辑与预算控制

4.1 遍历购买过程

排好序后，就可以按顺序尝试购买商品了：

vector<string> purchasedItems; int remainingBudget = budget; for(int i = 0; i < itemCount; i++) { if(products[i].price <= remainingBudget) { purchasedItems.push_back(products[i].name); remainingBudget -= products[i].price; } }

这里我使用了vector来动态存储购买的商品名，因为它比数组更灵活，不需要预先知道会买多少件商品。在实际项目中，这种动态数据结构的选择很重要。

4.2 边界条件处理

有几个边界情况需要注意：

预算为0时应该不购买任何商品
商品价格为0时应该可以无限购买（虽然题目保证1≤Pi）
所有商品价格都超过预算时应该输出空

虽然题目已经给出了一些数据范围的保证，但在实际开发中养成考虑边界条件的习惯很重要。

5. 结果输出与优化

5.1 最终排序输出

题目要求最终输出按字典序排列，所以我们需要对购买的商品名再次排序：

sort(purchasedItems.begin(), purchasedItems.end()); for(const auto& item : purchasedItems) { cout << item << endl; }

这里使用了C++11的范围for循环，代码更简洁。如果考试环境支持C++11，推荐使用这种写法。

5.2 算法优化思考

虽然这道题的数据规模(N≤1000)用O(nlogn)的排序算法完全足够，但我们可以思考一下更大数据量时的优化方案：

如果N很大(比如1e6)，可以考虑使用优先级队列(堆)来优化
如果商品优先级范围很小(题目中1≤Vi≤10)，可以使用计数排序来优化第一层排序
如果内存有限，可以考虑外部排序算法

这些优化思路虽然这道题用不上，但在实际工程问题和更高级的算法竞赛中可能会遇到。

6. 完整代码实现

结合以上所有部分，这是完整的解决方案：

#include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; struct Product { string name; int price; int priority; }; bool compareProducts(const Product& a, const Product& b) { if(a.priority != b.priority) return a.priority < b.priority; if(a.price != b.price) return a.price < b.price; return a.name < b.name; } int main() { int budget, itemCount; cin >> budget >> itemCount; Product products[1005]; for(int i = 0; i < itemCount; i++) { cin >> products[i].name >> products[i].price >> products[i].priority; } sort(products, products + itemCount, compareProducts); vector<string> purchasedItems; int remainingBudget = budget; for(int i = 0; i < itemCount; i++) { if(products[i].price <= remainingBudget) { purchasedItems.push_back(products[i].name); remainingBudget -= products[i].price; } } sort(purchasedItems.begin(), purchasedItems.end()); for(const auto& item : purchasedItems) { cout << item << endl; } return 0; }

7. 测试与调试技巧

7.1 测试用例设计

为了验证代码的正确性，我设计了几个测试用例：

基础测试：使用题目给的样例输入，验证输出是否正确
边界测试：预算为0、商品价格为预算刚好够、商品价格超过预算等情况
多优先级测试：验证多个相同优先级商品的排序是否正确
字典序测试：验证名字排序是否正确

例如这个测试用例：

10 3 banana 5 1 apple 5 1 orange 10 2

正确输出应该是：

apple banana

因为两个优先级为1的商品价格相同，按字典序apple排在banana前面，且orange因为价格等于预算但不能和前面的商品一起购买。

7.2 调试技巧

在考试环境下调试有几个实用技巧：

使用cerr输出中间结果，不会影响正式输出
对于排序问题，可以先输出排序后的序列，验证排序是否正确
对于边界情况，可以单独写小测试验证

比如可以在排序后添加调试输出：

cerr << "排序后商品列表：" << endl; for(int i = 0; i < itemCount; i++) { cerr << products[i].name << " " << products[i].price << " " << products[i].priority << endl; }