POJ-1456-Supermarket-超市-（贪心+优先队列）
POJ-1456-贪心算法+优先队列
Supermarket
超市
Description
描述
A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling schedule is an ordered subset of products Sell ≤ Prod such that the selling of each product x∈Sell, according to the ordering of Sell, completes before the deadline dx or just when dx expires. The profit of the selling schedule is Profit(Sell)=Σx∈Sellpx. An optimal selling schedule is a schedule with a maximum profit.
For example, consider the products Prod={a,b,c,d} with (pa,da)=(50,2), (pb,db)=(10,1), (pc,dc)=(20,2), and (pd,dd)=(30,1). The possible selling schedules are listed in table 1. For instance, the schedule Sell={d,a} shows that the selling of product d starts at time 0 and ends at time 1, while the selling of product a starts at time 1 and ends at time 2. Each of these products is sold by its deadline. Sell is the optimal schedule and its profit is 80.
POJ 一个学习英语的好地方，哈哈哈=(￣︶￣)=
参考翻译：（水平有限，欢迎批评）
一家超市有一套商品Prod待售。它每个商品 x∈Prod 的盈利为 px ，期限 dx 是从销售开始就被计算的一个整数时间单位。每件商品需要精确地占用一个单位的时间以被销售。一个销售时间表是商品 Sell ≤ Prod 的一个有序子集，以便于每件商品 x∈Prod
的销售根据 Sell 排序，需在期限dx之前或者就在dx到期时完成。销售时间表的好处是 Profit(Sell)=Σx∈Sellpx。一个最优的销售时间表是个可以利润最大化的时间表。
举个例Prod={a,b,c,d}, (pa,da)=(50,2) , (pb,db)=(10,1) , (pc,dc)=(20,2) , (pd,dd)=(30,1) .可能的销售时间表被罗列在表1。例如，时间表Sell = {d，a}表示商品 d 的 销售从时间0开始，到时间1结束，而商品 a 的销售从时间1开始，到时间2结束。这些商品的每一件都在截止前销售。Sell 是最优时间表，且利润为80。
编写一个程序，从输入的文本文件中读取多组产品，并计算每组产品的最佳销售时间表的利润。
输入
一组产品以0 <= n <= 10000的整数开始，该整数是该组中的产品的数量，并且继续n组整数pi di，1 <= pi <= 10000和1 <= di <= 10000，表示第i种产品的利润和销售期限。输入空白可以自由发生。输入数据以文件结尾终止并保证正确。
产量
对于每一组产品，该程序在标准输出上打印该组的最佳销售时间表的利润。每个结果都从单独一行的开头打印。
示例输入
4 50 2 10 1 20 2 30 1
720 1 2 1 10 3 100 2 8 25 20 50 10
示例输出
80
185
暗示
样本输入包含两个产品组。第一组编码表1中的产品。第二组编码7个产品。这些产品的最佳时间表的利润是185。
资源
分析：
题目大意是： 超市有堆商品要卖，但是它们有不同的利润和期限，得在此期限前卖出去，不一定要全部卖出，但是要求利润可以最大化。这些商品是从同一天开始一起贩卖的，每天只能卖一种商品。
比如这堆商品分为a,b,c,d四种
(pa,da)=(50,2) , (pb,db)=(10,1) , (pc,dc)=(20,2) , (pd,dd)=(30,1)
总共卖的天数=商品中期限最长的时间，所以为2天
0-1第1天d=30(要把a留到第二天卖，所以只有三种可以选，同选利润最大的)
0-2第2天a=50(只有a和c可以卖，选择利润最大的)
这是典型的贪心算法问题（活动安排）+优先队列。
输入不定测试组，以文件结尾结束，每组先输入一个n，然后是输入n组 pi di ，表示第 i 个商品的利润和 deadline
1. 按照 dx 和 px 从大到小排序
2. 建立优先队列 big
3. 从截止日期开始一天一天往前找截止日期内的，且还没有被卖过的，利润最大的商品
4. 在 big 中 push() 进 day 到 最大截止日期的所有商品的利润值
5. 注意不要重复压入哦
再举个例吧：
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10
排序后：
5 20
50 10
10 3
100 2
8 2
20 1
2 1
第20天时选择最大利润商品，即x[0].dx ，第11-19天，无商品可卖。。。第10天选50，第三天选10。。。
最后结果为：20+100+10+50+5=185
AC代码：
#include<iostream>
#include<queue>
#include<algorithm>
#define maxn 100001
using namespace std;
int out[maxn],longth=0;
class X
{
public:
int px;
int dx;
};
bool sort_dx_px(const X &x1,const X &x2)
{
if(x1.dx>x2.dx) return true;
else if(x1.dx==x2.dx)
{
if(x1.px>x2.px)
return true;
else
return false;
}
else
return false;
}
int main()
{
int n=0;
while(scanf("%d",&n)!=EOF)
{
X *x=new X[n]; //动态构建，节约空间
int maxx=0; //当前数据组的最大利润
if(n==0)
{
out[longth++]=0;
continue;
}
for(int i=0;i<n;i++)
cin>>x[i].px>>x[i].dx;
sort(x,x+n,sort_dx_px); // 按照 dx 和 px 从小到大排列
priority_queue<int> big; //优先队列
//从截止日期 一天一天 往前找 期限内的利润最大的商品
int i=0;
for(int day=x[0].dx;day>0;day--)
{
for(;i<n&&day<=x[i].dx;i++)
{
if(day>x[i].dx) break;
big.push(x[i].px);
}
while(!big.empty())
{
maxx+=big.top();
big.pop();break;
}
}
out[longth++]=maxx;
delete[] x; //消除内存空间
}
for(int i=0;i<longth;i++)
{
cout<<out[i]<<endl;
}
return 0;
}
测试数据
input：
0
4 50 2 10 1 20 2 30 1
4 50 2 10 1 15 2 27 1
5 1 3 15 2 5 3 20 2 10 1
720 12 110 3100 28 25 2050 10
10
13 2
18 1
68 10
72 8
11 7
41 2
48 7
15 7
34 1
13 8
5
3 2
65 1
61 3
60 2
86 1
output：
0
80
77
40
185
302
207