G4022 [GESP202512 四级] 优先购买 题解

知识点：多关键字排序、贪心模拟、字符串排序。

解题思路

将商品按优先级、价格、名称字典序升序排序，依次在预算够时买入并扣款，最后把买到的名称排序输出。

为什么正确

排序顺序正好对应购物优先规则，逐项扣款模拟唯一确定的购买过程，最后名称排序落实输出要求。

易错点

购买顺序与输出顺序不同；买不起某件时跳过，不停止检查后续商品。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m,n;
    cin>>m>>n;
    vector<tuple<int,int,string>>a;
    while(n--) {
        string s;
        int p,v;
        cin>>s>>p>>v;
        a.emplace_back(v,p,s);
    }
    sort(a.begin(),a.end());
    vector<string>ans;
    for(auto [v,p,s]:a)if(p<=m) {
        m-=p;
        ans.push_back(s);
    }
    sort(ans.begin(),ans.end());
    for(auto s:ans)cout<<s<<"\n";
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。