简答题 偏难
#19863

优先购买 时间限制 :1.0 s 内存限制 :512.0 MB 题目描述 小 A 有M元预算。商店有N个商品,每个商品有商品名S 、价格P和优先级V三种属性,其…

优先购买

时间限制:1.0 s

内存限制:512.0 MB

题目描述

小 A 有M元预算。商店有N个商品,每个商品有商品名S 、价格P和优先级V三种属性,其中V为正整数,且V越小代表商品的优先级越高。

小 A 的购物策略为:

总是优先买优先级最高的东西;

如果有多个最高优先级商品,购买价格最低的;

如果有多个优先级最高且价格最低的商品,购买商品名字典序最小的。

小 A 想知道能购买哪些商品。

输入格式

第一行两个正整数 M,N,代表预算和商品数。

之后N行,每行一个商品,依次为Si,Pi,Vi ,代表第 个商品的商品名、价格、优先级。数据保证不存在两个名字相同的商品。

输出格式

按照字典序从小到大的顺序,输出所有购买商品的商品名。

输入样例

20 4
apple 6 8
bus 15 1
cab 1 10
water 4 8

输出样例

bus
cab
water

数据范围

对于所有测试点,保证商品名仅由小写字母组成且不存在两个相同的商品名。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;string&gt; #include &lt;map&gt; #include &lt;assert.h&gt; using namespace std; struct Item {     string name;     int price;     int priority; }; bool cmp(const Item &amp;a, const Item &amp;b) {     if (a.priority != b.priority)         return a.priority &lt; b.priority;     if (a.price != b.price)         return a.price &lt; b.price;     return a.name &lt; b.name; } string s[1005]; std::map&lt;string, int&gt; mp; int main() {     int M, N;     cin &gt;&gt; M &gt;&gt; N;     Item items[N];          for (int i = 0; i &lt; N; ++i) {         cin &gt;&gt; items[i].name &gt;&gt; items[i].price &gt;&gt; items[i].priority;         assert(mp.find(items[i].name) == mp.end());         mp[items[i].name] = items[i].priority;     }          sort(items, items + N, cmp);     int budget = M;     int count = 0;          for (int i = 0; i &lt; N; ++i) {         if (items[i].price &lt;= budget) {             budget -= items[i].price;             s[count++] = items[i].name;         }     }          sort(s, s + count);     for (int i = 0; i &lt; count; ++i) {         cout &lt;&lt; s[i] &lt;&lt; endl;     }          return 0; }</pre>
这道题暂未补解析。