题目大意
一家超市，要卖出N种物品（每种物品各一个），每种物品都有一个卖出截止日期Di（在该日期之前卖出可以获得收益，否则就无法卖出），且每种物品被卖出都有一个收益值Pi. 卖出每个物品需要耗时1天，且任一时刻只能卖出一个物品。给出这N种物品的Di和Pi，求最大收益值。
题目分析
求最优值问题，可以考虑动态规划、贪心、搜索+剪枝等算法。尝试用贪心法来分析。
题目是要卖出物品，每天只能卖出一个，最多只能卖出X个（X为所有物品中最大的deadline值）。考虑第D天，需要卖出哪个物品呢？ 如果D从1到X考虑，会比较乱，因为第1天可以卖出所有N个物品（因为他们的deadline都大于等于1），此时不能直接挑选价值最大的那个进行售出（因为价值最大的那个的deadline可能会很大，第一天就将其售出可能导致其他deadline比较小的物品无法售出而造成损失。极端一点，价值最大的物品的deadline就是X，那么我们完全可以将价值最大的那个放在最后售出）；而如果D从X到1考虑，则会比较容易：对于第D天，我们只能卖出deadline在D以及D之后的那些物品，可以从中选择价值最大的进行售出，因为继续考虑更小的D时，第D天可以卖出的物品仍然可以在比D小的那天卖出（而D从1到X的情形中，第D天可以卖出的物品，在第D+1天可能无法卖出），这样成了一个，在每天的可选集合中进行选择，得到最大值的问题。
日期D从X到1递减，对于每个D，都存在可以被卖出的物品的集合S（满足物品的售出截止日期大于等于D即可），从这些物品中选取出来收益最大的那个物品A，进行售出，同时将A从S中消除；D每次减1的时候，可能导致有更多的物品可以被售出，则将这些物品加入集合S，同时从S中选出最大收益的那个进行售出，并剔除集合.....
由于需要选择集合S中收益最大的那个物品，因此使用优先队列进行维护。
实现（c++)
#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<set>
#include<map>
#include<functional>
#include<algorithm>
using namespace std;
struct Node{
int profit;
int deadline;
Node(int p=0, int d=0) :profit(p), deadline(d){};
};
Node gNodes[10005];
int solve(int n){
int cur_day = gNodes[n - 1].deadline;
int cur_product = n - 1;
priority_queue<int> pq;
int result = 0;
while (cur_day && cur_product >= 0){
while (cur_product >= 0 && gNodes[cur_product].deadline >= cur_day){
pq.push(gNodes[cur_product].profit);
cur_product--;
}
if (!pq.empty()){
result += pq.top();
pq.pop();
cur_day--;
}
else{
cur_day = gNodes[cur_product].deadline;
}
}
while (cur_day && !pq.empty()){
result += pq.top();
pq.pop();
cur_day--;
}
return result;
}
bool cmp(const Node& node1, const Node& node2){
return node1.deadline < node2.deadline;
}
int main(){
int n;
while (scanf("%d", &n) != EOF){
for (int i = 0; i < n; i++){
scanf("%d %d", &gNodes[i].profit, &gNodes[i].deadline);
}
sort(gNodes, gNodes + n, cmp);
int result = solve(n);
printf("%d
", result);
}
return 0;
}