A32863. Rainbow的商店Rainbow开了一家商店，在一次进货中获得了N个商品。已知每个商品的利润和过期时间。Rainbow每天只能卖一个商品，并且过期商品不能再卖。Rainbow也可以选择在每天出售哪个商品，并且一定可以卖出。由于这些限制，Rainbow需要制定一份合理的售卖计划。请你计算一下，Rainbow最终可以获得的最大收益。输入第一行两个整数N。 接下来N行每行两个整数，分别表示每个商品的…
填空题
困难
知识点
题目描述
Rainbow的商店
Rainbow开了一家商店，在一次进货中获得了N个商品。
已知每个商品的利润和过期时间。
Rainbow每天只能卖一个商品，并且过期商品不能再卖。
Rainbow也可以选择在每天出售哪个商品，并且一定可以卖出。
由于这些限制，Rainbow需要制定一份合理的售卖计划。请你计算一下，Rainbow最终可以获得的最大收益。
输入
第一行两个整数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件商品由于过期、每天只能卖一个的限制，在最优策略下应该不出售。
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
struct product{// product记录商品的价值和过期时间
int v;
int t;
}p[10005];
int visited[10005]; // 记录某天是否已经安排出售其他商品
bool mycmp( struct product& a, struct product& b ){ // 定义比较函数
return a.v > b.v || a.v == b.v && a.t < b.t;
}
int main(){
int n;
scanf("%d",&n);
for( int i = 0; i < n; ++i )
scanf("%d %d",&p[i].v,&p[i].t);
sort(p,p+n,mycmp); // 排序
int j = 0, ans = 0;
while( j < n ){ // 贪心
for( int i = p[j].t; i > 0 ; --i ){ // 向前遍历，直到找到可以安排出售该商品的时间
if( !visited[i] ){
ans += p[j].v;
visited[i] = 1;
break;
}
}
++j;
}
printf("%d",ans);
return 0;
}
上一题
下一题