题目链接：http://poj.org/problem?id=1456
题目大意：
有n件物品（n<=10000）每一件物品都有利润和过期时间，而且一天只卖一件物品。
过期时间<=10000
求最大利润。
题目思路：
首先贪心是最直接的想法，从利润大的开始处理，即按照利润降序排序一下。
处理过程：
（1）如果过期时间未被占用，就在最后的时间卖，因为这样就可能空出更多的时间卖别的。
（2）如果过期时间被占用，那么就往前找，找到一个离过期时间最近的且没有卖东西的时间卖。
显然第2步的复杂度是O（n）的,纯暴力，很显然复杂度是O（n*n）的，肯定要TLE的，但是这题的数据比较水，
肯定没有一组这种数据。
10000
10000 10000
9999 10000
9998 10000
9997 10000
...
1 10000
那么如何优化呢？
就拿上面的那组数据，
第一个商品在10000时卖掉，那么这时我们知道如果下次遇到10000就让它在9999的时候卖，所以我们可以用并查集。
比如在x的时候卖掉一件物品，就让x ---> x-1。
这样第二步的时候我们只要找到过期时间指向的祖先即可，祖先便是要卖的时间，这个操作是O（1）的。
代码：
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll __int64
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define eps (1e-8)
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define MOD (1000000007)
#define inf (0x3f3f3f3f)
#define pi (acos(-1.0))
#define _max(x,y) (((x)>(y))? (x):(y))
#define _min(x,y) (((x)<(y))? (x):(y))
#define _abs(x) ((x)<0? (-(x)):(x))
#define getmin(x,y) (x= (x<0 || (y)<x)? (y):x)
#define getmax(x,y) (x= ((y)>x)? (y):x)
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
int TS,cas=1;
const int M=10000+5;
int n,fa[M];
struct node{
int p,d;
void read(){scanf("%d%d",&p,&d);}
bool operator <(const node& t) const{
return p > t.p;
}
}a[M];
int find(int x){
return (fa[x]==x)? x:(fa[x]=find(fa[x]));
}
void run(){
int i,j;
for(i=1;i<=n;i++) a[i].read();
sort(a+1,a+n+1);
for(i=1;i<M;i++) fa[i]=i;
int sum=0;
for(i=1;i<=n;i++){
if(!(j=find(a[i].d))) continue;
sum+=a[i].p;
fa[j]=j-1;
}
printf("%d\n",sum);
}
void preSof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
preSof();
//run();
while(~scanf("%d",&n)) run();
//for(scanf("%d",&TS);cas<=TS;cas++) run();
return 0;
}