首页 › 题库 › C/C++编程考级 › C/C++编程八级 › 简答题
简答题 偏难
#7468

Rainbow的商店(2024.3八级) Rainbow开了一家商店,在一次进货中获得了N个商品。 已知每个商品的利润和过期时间。 Rainbow每天只能卖一个…

Rainbow的商店(2024.3八级)

Rainbow开了一家商店,在一次进货中获得了N个商品。

已知每个商品的利润和过期时间。

Rainbow每天只能卖一个商品,并且过期商品不能再卖。

Rainbow也可以选择在每天出售哪个商品,并且一定可以卖出。

由于这些限制,Rainbow需要制定一份合理的售卖计划。请你计算一下,Rainbow最终可以获得的最大收益。

时间限制:1000

内存限制:262144

输入

第一行两个整数N。 接下来N行每行两个整数,分别表示每个商品的利润、过期时间。 1<=N,利润,时间<=10000。

输出

输出一个整数,表示Rainbow最终可以获得的最大收益。


样例输入

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

样例输出

185


提示

第1天卖出20 第2天卖出100 第3天卖出10 第4天卖出50(实际上只要在第10天卖就可以) 第5天卖出5(实际上只要在第20天前卖就可以) 总计185 其它2件商品由于过期、每天只能卖一个的限制,在最优策略下应该不出售。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;algorithm&gt; #include&lt;queue&gt; #pragma warning (disable:4996); using namespace std; int N; struct Goods { int w; int d; friend bool operator &lt;(const Goods a, const Goods b) { if (a.w != b.w) { return a.w &lt; b.w;//大的天数小的在前 } else { return a.d &gt; b.d; } } }good[10005]; bool vis[10005] = {}; int main() { cin &gt;&gt; N; priority_queue&lt;Goods&gt;que; int maxval=0; for (int i = 1; i &lt;= N; i++) { scanf("%d %d", &amp;good[i].w, &amp;good[i].d); que.push(good[i]); } while (!que.empty()) { Goods now = que.top(); que.pop(); for (int i = now.d; i &gt;= 1; i--) { if (!vis[i]) { vis[i] = 1; maxval += now.w; break; } } } printf("%d\n", maxval); return 0; }</pre>
这道题暂未补解析。