简答题
偏难
#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<iostream>
#include<algorithm>
#include<queue>
#pragma warning (disable:4996);
using namespace std;
int N;
struct Goods
{
int w;
int d;
friend bool operator <(const Goods a, const Goods b)
{
if (a.w != b.w)
{
return a.w < b.w;//大的天数小的在前
}
else
{
return a.d > b.d;
}
}
}good[10005];
bool vis[10005] = {};
int main()
{
cin >> N;
priority_queue<Goods>que;
int maxval=0;
for (int i = 1; i <= N; i++)
{
scanf("%d %d", &good[i].w, &good[i].d);
que.push(good[i]);
}
while (!que.empty())
{
Goods now = que.top();
que.pop();
for (int i = now.d; i >= 1; i--)
{
if (!vis[i])
{
vis[i] = 1;
maxval += now.w;
break;
}
}
}
printf("%d\n", maxval);
return 0;
}</pre>
这道题暂未补解析。