本文主要是介绍Rainbow的商店，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Rainbow的商店
总时间限制:
1000ms
内存限制:
262144kB
描述
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件商品由于过期、每天只能卖一个的限制，在最优策略下应该不出售。
思路：
看到了这道题，我第一个想到的不是排序，而是贪心， 于是我就决定先用贪心算法实现，如果实在不行就想一下怎么排序，接下来我就给大家讲我贪心的思路：
贪心比较特殊，要让最大的卖出去，又尽量不能让小的过期，只按照价值排遇到保质期大的大值就会出问题
最后思路是：大的在前，价值一样的话天数少的在前，但其实没有影响
设立vis数组表示某天是不是被占用，从最大的d开始，向前找有没有未占用的天数
然后设立一个结构good，里面是一个物品的利润和过期时间，然后说明一下调用排序的。
之后利用STL库里面的priority_queue的一个类（就是优先队列），将其变量设为这个结构，之后按照贪心的思想进行入队和出队。
代码：
#include<bits/stdc++.h>
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 sum=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;sum+=now.w;break;}}}printf("%d\n",sum);return 0;
}这道题的算法标签虽然是排序，但是也可以经过思考，换一种算法来进行解决！
改题链接：
OpenJudge - 9:Rainbow的商店
这篇关于Rainbow的商店的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
