优先购买 题解

一、题目分析

小 A 有 (M) 元预算，商店有 (N) 个商品，每个商品有商品名、价格和优先级三种属性。优先级用一个正整数 (V) 表示，(V) 越小优先级越高。小 A 的购物策略是：

1. 优先购买优先级最高的商品（即 (V) 最小）；
2. 如果有多个优先级相同的商品，优先购买价格最低的；
3. 如果优先级和价格都相同，优先购买商品名字典序最小的。

小 A 会根据自己的预算，按照上述策略依次尝试购买商品，直到预算不足或没有能买的商品为止。题目要求输出所有被购买的商品名，按照字典序从小到大的顺序输出。

数据范围：(1 \le N \le 10^3)，(1 \le M, P_i \le 10^5)，(1 \le V_i \le 10)，商品名由小写字母组成且长度不超过 (10)，保证不存在两个名字相同的商品。

二、解题思路

这道题的核心在于按照给定策略对商品进行排序，然后模拟购买过程，最后按题目要求输出结果。

我们可以这样思考：

1. 先将所有商品按照优先级 (V) 从小到大排序；
2. 对于优先级相同的商品，按照价格从小到大排序；
3. 对于优先级和价格都相同的商品，按照商品名字典序从小到大排序。

经过这样排序后，数组中的商品顺序就是小 A 的理想购买顺序。我们只需要从头到尾遍历排序后的商品列表，如果当前预算足够购买该商品，就将其买下（记录商品名，并减去对应价格）；如果不够，就跳过它，继续看后面的商品（因为后续商品优先级可能相同或更低，但不能再买前面的了，跳过即可）。

当所有商品遍历完，或者预算不足以购买任何剩余商品时，模拟结束。最后，把成功购买的商品名再按照字典序排序并输出，即可得到答案。

由于 (N) 最多只有 (1000)，使用 (O(N \log N)) 的排序完全可行，甚至可以接受一些简单的多重排序。

三、算法说明

1. 数据结构

定义一个结构体 Item 来存储每个商品的信息：

cpp
复制
1struct Item {
2    string name;   // 商品名
3    int price;     // 价格
4    int priority;  // 优先级
5};

2. 自定义比较函数

根据题目给出的购买策略编写排序规则：

cpp
复制
1bool cmp(const Item &a, const Item &b) {
2    if (a.priority != b.priority) 
3        return a.priority < b.priority;   // 优先级越小越靠前
4    if (a.price != b.price) 
5        return a.price < b.price;         // 价格越低越靠前
6    return a.name < b.name;              // 字典序越小越靠前
7}

3. 模拟购买

用变量 budget 记录当前剩余预算，初始值为 (M)。遍历排序后的商品数组，若某商品的 price <= budget，则购买它，将其名字存入一个字符串数组 s 中，并从预算中扣除相应价格。

4. 输出结果

题目要求按照字典序从小到大输出购买的商品名，所以对 s 数组进行排序后逐行输出即可。

四、时间复杂度分析

• 对 (N) 个商品排序：(O(N \log N))。
• 模拟购买过程：遍历一遍商品，(O(N))。
• 对购买的商品名排序：假设买了 (K) 个商品，(K \le N)，复杂度 (O(K \log K))。
• 总时间复杂度为 (O(N \log N))，在 (N \le 1000) 的数据规模下非常高效。

空间复杂度主要为存储商品和名字的数组，为 (O(N))。

五、参考代码及解释

cpp
复制
1#include <iostream>
2#include <algorithm>
3#include <string>
4#include <map>
5#include <assert.h>
6using namespace std;
7
8struct Item {
9    string name;
10    int price;
11    int priority;
12};
13
14// 自定义排序规则
15bool cmp(const Item &a, const Item &b) {
16    if (a.priority != b.priority) return a.priority < b.priority;
17    if (a.price != b.price) return a.price < b.price;
18    return a.name < b.name;
19}
20
21string s[1005];               // 存储购买的商品名
22map<string, int> mp;          // 用于检查商品名是否重复（题目保证不重复，此处为断言）
23
24int main() {
25    int M, N;
26    cin >> M >> N;
27    Item items[N];
28    
29    for (int i = 0; i < N; ++i) {
30        cin >> items[i].name >> items[i].price >> items[i].priority;
31        // 断言：确保没有两个同名的商品
32        assert(mp.find(items[i].name) == mp.end());
33        mp[items[i].name] = items[i].priority;
34    }
35    
36    // 按照购买策略排序
37    sort(items, items + N, cmp);
38    
39    int budget = M;
40    int count = 0;
41    
42    // 模拟购买过程
43    for (int i = 0; i < N; ++i) {
44        if (items[i].price <= budget) {
45            budget -= items[i].price;
46            s[count++] = items[i].name;   // 记录购买的商品名
47        }
48    }
49    
50    // 对购买的商品名进行字典序排序
51    sort(s, s + count);
52    for (int i = 0; i < count; ++i) {
53        cout << s[i] << endl;
54    }
55    
56    return 0;
57}

代码细节说明

• assert 部分用于在调试时确保题目条件“不存在两个名字相同的商品”，在实际比赛中如果数据严格满足条件也可以省略。
• mp 在这里仅用于断言检查，对解题逻辑本身没有影响，可以完全去掉。
• 模拟购买时，使用 count 记录实际购买的商品数量，最后只对前 count 个名字排序输出，避免输出空串。
• 最终输出的商品名已经按照字典序排列，符合题目要求。

六、总结

本题是一道典型的“排序 + 模拟”题目，重点在于理解多重排序的规则，并正确实现比较函数。在模拟购买时，因为购买顺序已经由排序决定，所以直接贪心选取即可。最后别忘了按照题目要求的字典序输出结果。整体难度不大，适合用来练习结构体排序与简单贪心策略的应用。