【题解】POJ P1456 【Supermarket】

【算法】贪心

【题意】一家超市,要卖出n个物品,每种物品都有一个过期时间d_{i},和一个收益p_{i},卖出每个物品耗时一天,且任意时刻只能卖出一个物品(这超市迟早倒闭233),求最大收益。

【分析】

求最优值可以贪心和DP,这题显然满足贪心性质。

每天只能卖一个,最多就只能卖d_{max}个。考虑第i天,如果i从1到d_{max}枚举就比较乱,所以咱们让id_{max}到1考虑。对于第i天,都存在可以被卖出的物品集合S(满足物品过期时间大于i即可),从S中选出最大收益那个物品A,卖掉(从S中删除),以此类推。

显然S应该用优先队列维护。

p.s.好像我调STL的函数做的堆还跑不过priority_queue,,,qwq

#include<cstdio>
#include<vector>
#include<algorithm>
#include<functional>

namespace OI{
	using std::vector;
	using std::greater;
	using std::less;
	using std::make_heap;
	using std::pop_heap;
	using std::push_heap;
	using std::sort;
}
using namespace OI;

template<class T>
class Heap{
	public:vector<T> v;
	
	public:Heap(){
		v.reserve(1000000);
	}
	public:~Heap(){}
	
	public:void push(T key){
		v.push_back(key);
		//push_heap(v.begin(),v.end(),greater<T>());
		push_heap(v.begin(),v.end(),less<T>());
	}
	
	public:void pop(){
		pop_heap(v.begin(),v.end(),less<T>());
		//pop_heap(v.begin(),v.end(),greater<T>());
		v.pop_back();
	}
	
	public:T front(){
		return v[0];
	}
	
	public:bool isEmpty(){
		return v.empty();
	}
};

class Goods{
	public:int p,d;
	
	public:Goods(){}
	public:Goods(int p,int d){
		this -> p = p;
		this -> d = d;
	}
	public:~Goods(){}
};

bool cmp(Goods g1,Goods g2){
	if(g1.d == g2.d){
		return g1.p < g2.p;
	}else{
		return g1.d < g2.d;
	}
}
Goods g[10000 + 6];

int main(){
	int n;
	while(scanf("%d",&n) != EOF){
		int p,d;
		for(int i = 0;i < n;i++){
			scanf("%d %d",&p,&d);
			g[i] = Goods(p,d);
		}
		
		sort(g,g + n,cmp);
		Heap<int> h;
		
		int currentD = g[n - 1].d;
		int currentP = n - 1;
		int ans = 0;
		while(currentD && currentP >= 0){
			while(currentP >= 0 && g[currentP].d >= currentD){
				h.push(g[currentP].p);
				currentP--;
			}
			
			if(!h.isEmpty()){
				ans += h.front();
				h.pop();
				currentD--;
			}else{
				currentD = g[currentP].d;
			}
		}
		
		while(currentD && !h.isEmpty()){
			ans += h.front();
			h.pop();
			currentD--;
		}
		
		printf("%d\n",ans);
	}
	
	return 0;
}