按"优先级最高 → 价格最低 → 名字字典序最小"的顺序反复购买,直到买不起为止。
小 A 有 M 元预算。商店有 N 个商品,每个商品有名字 S、价格 P、优先级 V 三个属性,V 越小优先级越高。购物策略为:
请按字典序从小到大输出所有买到的商品名。
多关键字排序贪心预算约束字典序输出
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 M、N;随后 N 行每行 S、P、V |
| 输出 | 买到的商品名,按字典序升序,每行一个 |
| 数据范围 | N ≤ 1000,M, P ≤ 10⁵ |
| 优先级 | 1 ≤ V ≤ 10,V 越小越优先 |
| 保证 | 商品名互不相同,仅含小写字母,长度 ≤ 10 |
商品列表:
| 商品名 | 价格 P | 优先级 V |
|---|---|---|
| apple | 6 | 8 |
| bus | 15 | 1 |
| cab | 1 | 10 |
| water | 4 | 8 |
| 排序后顺序 | 商品 | V | P | 说明 |
|---|---|---|---|---|
| 1 | bus | 1 | 15 | V 最小,优先级最高 |
| 2 | water | 8 | 4 | V 相同比价格,4 < 6 |
| 3 | apple | 8 | 6 | 与 water 同 V,价格更大 |
| 4 | cab | 10 | 1 | V 最大,排最后 |
预算 20 ≥ 15 → 买
预算变为 20 − 15 = 5
已买:bus
预算 5 ≥ 4 → 买
预算变为 5 − 4 = 1
已买:bus、water
预算 1 < 6 → 买不起,跳过
跳过
预算 1 ≥ 1 → 买
预算变为 0
已买:bus、water、cab
买到的商品是 bus、water、cab,按名字字典序排列:bus、cab、water。
bus cab water
按 (V,P,名字) 排序,然后顺序扫描买得起的
每买一件就重新遍历全部商品找当前最优
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 排序 + 扫描 | O(N log N) | 约 25 行 |
| 每轮重扫 | O(N²) | 约 30 行 |
第一行输入 M 和 N,随后 N 行每行一个商品(名字 价格 优先级)。
点按钮开始 →
#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()) | 输出前排序 | 输出要求字典序,与购买顺序无关 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
20 4 | bus cab water | 题面样例 |
5 1 | (无输出) | 预算不够,一件都买不起 |
10 2 | a b | 优先级价格都相同,按名字字典序先买 a |
3 3 | x y | 按优先级买 z、y,预算只剩 1,x 买不起 |
100 2 | aa ab | 同优先级同价格,名字小者优先买,但最终输出按字典序 |
M -= p,否则会把后面买不起的也买下来。需要存 N 个商品和购买清单。
✅ N 只有 1000,排序开销极小,瞬间完成。
// 字符串字典序比较 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()); // 按输出要求重新排序 // 贪心的常见前提 // 只要"选择顺序"与"资源消耗"单调相关,一趟扫描就等价于反复挑最优
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 多关键字排序 | 优先级 → 价格 → 名字 | 电商推荐、任务调度、排行榜 |
| 贪心购买 | 顺序扫描,买得起就买 | 预算分配、背包简化版 |
| 输出顺序重排 | 购买顺序 ≠ 输出顺序 | 所有"按规则选、按要求输出"的题 |