A105543 题解 202512四级

题目回顾

小A有 ( M ) 元预算，商店有 ( N ) 个商品。每个商品有名字、价格和优先级（数字越小越优先）。
小A每次从还没买的商品中，按照以下规则选一个购买：

1. 优先级最高的（V最小）
2. 如果并列，选价格最低的
3. 如果还并列，选名字字典序最小的

买完后钱减少，重复这个过程，直到剩下的商品都买不起为止。
最后，按名字字典序输出所有买到的商品。

代码思路

一次排序 + 一次顺序扫描：

1. 定义结构体 node 存储每个商品的名字 s、价格 p、优先级 v。
2. 自定义比较函数 cmp：
   • 先比优先级 v（越小越靠前）
   • 如果相同再比价格 p（越小越靠前）
   • 如果还相同再比名字 s（字典序小的靠前）
3. 排序：将全部商品按这个规则排序，排好后的数组 a[1..n] 中，越靠前的商品就是小A越优先想买的。
4. 模拟购买：按排序后的顺序，依次看每个商品：
   • 如果当前预算 m 大于等于商品价格，就买下（把名字加入 ve，然后预算减去价格）
   • 否则跳过（因为后面的商品要么优先级更低，要么价格更高，更买不起）
5. 输出：最后把所有买到的名字按字典序排序（题目要求），然后逐行输出。

为什么这样做是对的？

• 小A每一次都是选“优先级最高、价格最低、名字最小”的那个，这正好是排序后的第一个商品。
• 买完第一个后，剩下的商品中，排第二的商品就变成了“当前最好”的（因为排序已经保证了顺序）。
• 所以只要按排序后的顺序依次尝试购买，就能完美模拟小A的购物过程。
• 注意：如果当前商品买不起，那么后面的商品优先级相同或更低，价格也只会更贵（因为同优先级内价格已升序），所以更买不起，因此跳过是安全的。

代码+注释

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

int m, n;                     // m: 预算, n: 商品总数

struct node {
    string s;                 // 商品名
    int p;                    // 价格
    int v;                    // 优先级（越小越优先）
} a[1009];                    // 存储所有商品

// 自定义排序规则：按优先级升序 → 价格升序 → 名字升序
bool cmp(node x, node y) {
    if (x.v != y.v) return x.v < y.v;       // 优先级小的在前
    else if (x.p != y.p) return x.p < y.p;  // 价格小的在前
    return x.s < y.s;                       // 名字字典序小的在前
}

int main() {
    cin >> m >> n;            // 读入预算和商品数量
    for (int i = 1; i <= n; i++) {
        cin >> a[i].s >> a[i].p >> a[i].v;   // 读入每个商品
    }

    sort(a + 1, a + n + 1, cmp);   // 按小A的偏好排序

    vector<string> ve;             // 存放买到的商品名
    for (int i = 1; i <= n; i++) {
        if (m >= a[i].p) {         // 钱够就买
            ve.push_back(a[i].s);  // 记录商品名
            m -= a[i].p;           // 扣钱
        }
    }

    sort(ve.begin(), ve.end());    // 按名字字典序排序（题目要求）
    for (auto &i : ve) cout << i << "\n";   // 逐行输出

    return 0;
}

小提示

• 排序用了 sort(a+1, a+n+1, cmp)，因为数组下标从1开始。
• 用 vector<string> 来存买到的名字，方便最后排序。
• 最后输出时，auto &i 可以自动推断类型，等价于 string i。