本文主要是介绍284. 超市卖货-----HZOJ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目：
超市里有N个商品. 第i个商品必须在保质期(第di天)之前卖掉, 若卖掉可让超市获得pi的利润.
每天只能卖一个商品.
现在你要让超市获得最大的利润.
输入
每组数据第一行为一个整数N(0<N≤10000), 即超市的商品数目
之后N行，每行各有两个整数, 第i行为pi,di(1<=pi,di<=10000)
输出
输出当前条件下超市的最大利润.
二、样例：
输入：
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10
输出：
185
三、题目分析：
由题目可知，超市里有N个商品，第i个商品必须在保质期第di天前卖掉，比如说，假如有第7个商品，就要在第7天前（包括第7天）卖掉这个商品，一天只能卖一个商品。且，第di天卖的第i个商品必须让超市获得最大利润，也就是说，假如有7个商品，那么这7个商品必须在第7天前（包括第7天）卖掉并获得最大总利润。那么要最大总利润，就要卖掉的每个商品获得最大利润。
比如说：
上面的输入案例中，有两件还有一天就过期的商品。其中，一件商品利润为20，另一件利润为2，那么超市为了取得最大利润，就会上架可以获取利润为20的商品，以此类推。
最后的最大利润为：20(d1)+10(d3)+100(d2)+5(d20)+50(d10)=185
四、解决思路分析：
通过上面的题目分析，相信你已经对题目的要求有了一定的了解。在这个基础上，该如何编写代码来解决这个问题呢？
首先，我们需要输入一个数作为超市的商品数目，其次输入N行，各有两个整数, 第i行为pi,di(1<=pi,di<=10000)。根据题目要求，需要先对已经输入过期的天数或利润进行排序，再根据之后商品过期的天数和利润决定：
（1）如果商品的过期天数大于当前商品的最大过期天数第di天，则可以直接上架，因为超市可以在该商品的过期日期前卖掉；
（2）如果商品的过期天数等于当前商品的最大过期天数第di天，则替换掉已上架商品的利润最小者，利润大者上架。
（3）如果商品的过期天数小于当前商品的最大过期天数第di天，要么该商品已经上架，要么该商品已经过期，比如说，有一件将在3天后过期的商品上架了，这时来了一件将在2天后过期的商品，超市对已经快要过期的商品已经进行了过期天数和利润的排序，要么就已在餐桌上和菜单上了，要么就是已经过期了。
那么不用考虑最后一种情况。
在这个过程中，由于我们要对过期天数及利润进行从小到大的维护，所以需要使用一个排序算法或结构来维护。在这里，使用的是小顶堆(set有序集合）。
五、 代码及说明：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<stack>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<vector>
using namespace std;
typedef struct data{ //定义一个结构体作为一件商品data(int p,int d):p(p),d(d){} //定义一个有参构造方法，赋值int p; //商品的利润int d; //商品将在第d天后过期bool operator<(const data &obj)const{ //重载一个小于运算符if(d!=obj.d)return d<obj.d; //过期天数按照从小到大比较排序，同号<return p>obj.p; //商品利润按照从大到小排序，异号>}
}data;typedef pair<int,int>pir; //用于记录第几个商品的大利润，第一个参数为利润，第二个参数为第几个商品int main(){int n1;cin>>n1; //输入超市有n1个商品vector<data>arr;//用于存储这些商品set<pir>s;//小顶堆，用于存储上架最大利润，同时过期天数符合的商品for(int i=0,p,d;i<n1;i++){cin>>p>>d; //输入商品的利润、过期天数arr.push_back(data(p,d)); //存储这些商品信息}sort(arr.begin(),arr.end()); //根据重载方法对这些商品信息进行排序for(int i=0;i<n1;i++){if(arr[i].d>s.size()){ //该商品过期天数大于当前保质期第di天（保质期=1，则为1天,类比size)s.insert(pir(arr[i].p,i)); //存储商品的利润并按利润从小到大排序，及第几个商品}else if(arr[i].d==s.size()){ //过期天数等于当前保质期第di天if(arr[i].p>s.begin()->first){ //该商品利润大于上架商品最小利润s.erase(s.begin()); //删除已上架最小利润的商品s.insert(pir(arr[i].p,i)); //上架该商品}}}int ans=0;for(auto x:s){ //遍历已上架的商品ans+=x.first; //计算总最大利润}cout<<ans<<endl;return 0;
}文章到从结束！
这篇关于284. 超市卖货-----HZOJ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
