poj 1456 Supermarket

poj 1456 Supermarket

题意：给出一些商品的清单，清单上有每个商品能获得的利润和可以出售的最后期限，卖一件商品的恰好需要一天，问能获得的最大利润是多少。感觉每次读题都好痛苦啊。。。

思路：其实是蛮简单的贪心，感觉挺好玩就写发题解吧……可以想到，想要让利润最大就要让价值最大的产品尽可能多的卖出去，那么就要按照利润排个序，然后给每个产品安排一个合理的时间，所谓合理，也就是说在保证该产品能卖出的条件下，尽可能让其他产品也能卖出去，由于总共的天数不是很大，那么就可以用一个数组pre记录离这一天最近的一个没有安排出售商品的日期，刚开始还想着怎么推一下这个数组，后来突然反应过来，这用是并查集的Find函数不就可以搞定了么，想到这这题就很轻松啦~~~

代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn=10000+10;
struct Node
{int px,dx;bool operator < (const Node &a) const{return px>a.px;}
};
int pre[maxn];
Node node[maxn];
int Find(int x)
{return x==pre[x]?x:pre[x]=Find(pre[x]);
}
int main()
{//freopen(&#","r",stdin);//freopen(&#","w",stdout);int n;while(~scanf("%d",&n)){for(int i=0;i<maxn;++i) pre[i]=i;for(int i=0;i<n;++i)scanf("%d%d",&node[i].px,&node[i].dx);sort(node,node+n);int sum=0,tmp;for(int i=0;i<n;++i){tmp=Find(node[i].dx);if(tmp==0) continue;tmp=pre[node[i].dx];sum+=node[i].px;pre[tmp]=pre[tmp-1];}printf("%dn",sum);}return 0;
}