题意：
N个商品，每个在截止日期dx之前卖出，可以获得dp利润，问获得利润的最大值。
题解：
将商品按照dp排序，然后依次将商品放在截止日期当天卖出，如果后来的与前面的发生冲突（两个商品截止日期相同），然后往前查找没有卖商品的日期，去卖后来的那个商品。
这个思想和哈希表线性处理冲突的方法类似，可以直接定义个布尔数组used【n】，每次扫描到没有卖物品的日期，然后卖掉冲突的商品。既然这道题在并查集专题下了，就存在用并查集优化的方法。
并查集优化处理冲突:
说白了，这里的并查集实质上是线性链表的意思。
举个栗子：
第一个为截止日期为4的商品，然后直接在第findset（4）=4天卖出，然后pa[4]=3（4-1）；
第二个为截止日期为5的商品，然后直接在第findset（5）=5天卖出，然后pa[5]=4；
现在findsed(5)=3，
第三个为截止日期为5的商品，应该在第findset(5)=3天卖出。
再加上路径压缩带来的查找的高效，起到了优化效果。
所以这里的并查集实际上是一个处理冲突的一种方法。 #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #include<string> #include<cstring> #include<vector> #include<functional> #include<utility> #include<set> #include<map> #include<cmath> #include<stack> using namespace std; const int maxn=10000+5; int pa[maxn]; int findset(int x) { return pa[x]==-1? x : pa[x]=findset(pa[x]); } struct node { int px,dx; bool operator <(const node& a) { return px>a.px; } }a[maxn]; int main() { int n; while(cin>>n) { int res=0; memset(pa,-1,sizeof(pa)); for(int i=0;i<n;i++) cin>>a[i].px>>a[i].dx; sort(a,a+n); for(int i=0;i<n;i++) { int r=findset(a[i].dx); if(r>0) { pa[r]=r-1; res+=a[i].px; } } cout<<res<<endl; } }