GESP 题解库 / 4 级题解 / [GESP202512 四级] 优先购买 · 第 3 / 25 题
GESP202512 四级 · B4452 · 简单

优先购买

按"优先级最高 → 价格最低 → 名字字典序最小"的顺序反复购买,直到买不起为止。

📊
N ≤ 1000
商品数
💰
M ≤ 10⁵
预算
⚡
O(N log N)
时间复杂度
🎯
多关键字排序 + 贪心
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小 A 有 M 元预算。商店有 N 个商品,每个商品有名字 S、价格 P、优先级 V 三个属性,V 越小优先级越高。购物策略为:

请按字典序从小到大输出所有买到的商品名。

💡
人话翻译:把商品按 (V, P, 名字) 三级排序,然后从头到尾扫一遍,买得起就买、买不起就跳过。注意输出要按名字字典序,不是按购买顺序。

🔍 关键词提取

多关键字排序贪心预算约束字典序输出

已知条件

项目说明
输入第一行 M、N;随后 N 行每行 S、P、V
输出买到的商品名,按字典序升序,每行一个
数据范围N ≤ 1000,M, P ≤ 10⁵
优先级1 ≤ V ≤ 10,V 越小越优先
保证商品名互不相同,仅含小写字母,长度 ≤ 10

需要解决的问题

02
思维导图
整理解题思路的全貌
🛒 三级排序 + 一趟扫描
📥 读入
M 元预算
N 个商品(名、价、优先级)
V 越小越优先
名字互不相同
⚖️ 排序键
第一关键字 V 升序
第二关键字 P 升序
第三关键字 名字字典序
用结构体 + cmp
💰 贪心购买
按排序顺序扫描
M ≥ P 就买
预算减去 P
买不起就跳过
📤 输出
收集买到的商品名
再按名字字典序排序
每行一个
注意输出顺序≠购买顺序
03
样例手算推导
样例 4 个商品的购买过程

🧮 样例:预算 20 元

商品列表:

商品名价格 P优先级 V
apple68
bus151
cab110
water48

第一步:按 (V, P, 名字) 排序

排序后顺序商品VP说明
1bus115V 最小,优先级最高
2water84V 相同比价格,4 < 6
3apple86与 water 同 V,价格更大
4cab101V 最大,排最后

第二步:依次决定买不买

1
第 1 个:bus(15 元)

预算 20 ≥ 15 → 买

预算变为 20 − 15 = 5

已买:bus

2
第 2 个:water(4 元)

预算 5 ≥ 4 → 买

预算变为 5 − 4 = 1

已买:bus、water

3
第 3 个:apple(6 元)

预算 1 < 6 → 买不起,跳过

跳过

4
第 4 个:cab(1 元)

预算 1 ≥ 1 → 买

预算变为 0

已买:bus、water、cab

第三步:按字典序输出

买到的商品是 bus、water、cab,按名字字典序排列:bus、cab、water。

bus
cab
water
🔑
两个容易忽略的点:① 输出顺序是名字字典序,不是购买顺序(购买顺序是 bus、water、cab);② 排序键用 V 作第一关键字,所以在样例里最贵的 bus(15 元)反而最先被考虑——"优先级"比"价格"重要得多。
04
解法对比
排序后一趟扫描 vs 每轮重新找最优

⚔️ 解法对比

🟢 排序 + 一趟扫描(推荐) 推荐

按 (V,P,名字) 排序,然后顺序扫描买得起的

  • 时间 O(N log N)
  • 一次排序一次扫描
  • 代码简短
  • 无需重复查找
💡
为什么一趟扫描等价于"每轮重新找最优"?因为排序顺序是固定的,被跳过的商品在后续轮次里依然排在同一位置,所以"当前买得起的最优商品"就是排序序列里第一个未处理且买得起的。

🟠 每轮重新扫描找最优

每买一件就重新遍历全部商品找当前最优

  • 时间 O(N²)
  • N = 1000 时 10⁶ 次,也能过
  • 逻辑更贴近题面描述
  • 但代码更啰嗦
⚠️
都能过:N ≤ 1000 时即使 O(N²) 也够快。但从写法上看,排序法更简洁,也更容易理解"策略"的本质。

📈 性能对比

方案复杂度代码量
排序 + 扫描O(N log N)约 25 行
每轮重扫O(N²)约 30 行
05
算法流程图
排序 → 扫描 → 按名输出
开始读入预算 M 和 N 个商品按 (V 升序, P 升序, 名字升序) 排序按排序顺序取下一个商品预算 M ≥ 该商品价格吗?是 ✓买入:M 减去价格,记录名字否 ✗跳过该商品所有商品都看完了吗?把买到的商品名按字典序排序并输出结束还有商品 → 继续判断
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🛒 优先购买模拟器

第一行输入 M 和 N,随后 N 行每行一个商品(名字 价格 优先级)。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

struct Good {
    string name;
    int p;      // 价格
    int v;      // 优先级(越小越优先)
};

// 三级排序:优先级 -> 价格 -> 名字字典序
bool cmp(const Good &a, const Good &b) {
    if (a.v != b.v) return a.v < b.v;
    if (a.p != b.p) return a.p < b.p;
    return a.name < b.name;      // string 自带字典序比较
}

int main() {
    int M, N;
    scanf("%d %d", &M, &N);

    vector<Good> g(N);
    for (int i = 0; i < N; i++) {
        char buf[20];
        scanf("%s %d %d", buf, &g[i].p, &g[i].v);
        g[i].name = buf;
    }

    sort(g.begin(), g.end(), cmp);

    vector<string> bought;
    for (int i = 0; i < N; i++) {
        if (M >= g[i].p) {          // 买得起就买
            M -= g[i].p;
            bought.push_back(g[i].name);
        }
    }

    sort(bought.begin(), bought.end());   // 输出要求按字典序

    for (const string &s : bought) printf("%s\n", s.c_str());
    return 0;
}
🔑
为什么最后还要再排一次序?购买顺序是按"优先级"排的,而输出要求按"商品名字典序",这两个顺序完全不同,所以买完之后要把名字单独排序再输出。

📖 关键几行怎么看

代码作用为什么这样写
if (a.v != b.v) return a.v < b.v;优先级最高V 越小越优先,所以升序
return a.name < b.name;字典序C++ 的 string 直接用 < 就是字典序
if (M >= g[i].p)买得起判断注意每买一件预算就减少
sort(bought.begin(), bought.end())输出前排序输出要求字典序,与购买顺序无关
⚠️
三个坑:① 直接把购买顺序当输出顺序(样例里购买顺序是 bus、water、cab,但输出必须是 bus、cab、water);② 排序时把价格当成第一关键字(应该优先级优先);③ 忘记更新预算,导致后面错误地多买。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
20 4
apple 6 8 / bus 15 1 / cab 1 10 / water 4 8
bus
cab
water
题面样例
5 1
pen 6 1
(无输出)预算不够,一件都买不起
10 2
b 1 1 / a 1 1
a
b
优先级价格都相同,按名字字典序先买 a
3 3
x 1 3 / y 1 2 / z 1 1
x
y
按优先级买 z、y,预算只剩 1,x 买不起
100 2
aa 5 1 / ab 5 1
aa
ab
同优先级同价格,名字小者优先买,但最终输出按字典序
✅
自查清单:① 排序键是 V → P → 名字吗?② 每买一件都扣钱了吗?③ 输出按字典序排了吗?

🚨 易错点清单

⚠️
输出顺序错:必须是名字字典序,不是购买顺序。
⚠️
排序键顺序错:优先级是第一关键字,价格是第二关键字,不能颠倒。
⚠️
忘记扣预算:每买一件都要 M -= p,否则会把后面买不起的也买下来。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N log N)
空间复杂度
O(N)
N 最大
1000
预算 M
≤ 10⁵

时间怎么算的?

空间都用在哪?

需要存 N 个商品和购买清单。

✅ N 只有 1000,排序开销极小,瞬间完成。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 字符串字典序比较
if (a.name < b.name) { /* a 在前 */ }   // C++ string 直接用 < 比较
// C 风格字符串需要用 strcmp
if (strcmp(a, b) < 0) { /* a 在前 */ }

// 多关键字排序 + 输出前重排的通用套路
sort(goods.begin(), goods.end(), cmpBuyOrder);   // 按购买优先级排序
vector<string> chosen;
for (auto &x : goods) if (budget >= x.price) { budget -= x.price; chosen.push_back(x.name); }
sort(chosen.begin(), chosen.end());              // 按输出要求重新排序

// 贪心的常见前提
// 只要"选择顺序"与"资源消耗"单调相关,一趟扫描就等价于反复挑最优

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
多关键字排序优先级 → 价格 → 名字电商推荐、任务调度、排行榜
贪心购买顺序扫描,买得起就买预算分配、背包简化版
输出顺序重排购买顺序 ≠ 输出顺序所有"按规则选、按要求输出"的题
🌟
思考题:如果题目改成"买到的商品总数最多"(忽略优先级,只要求件数最多),策略要怎么变?(提示:那就应该优先买最便宜的,此时排序键要换成"价格升序",这是经典的贪心结论。)