悲剧呀，我怎么又理解错题意了，写了一个代码，固执的修改提交，都WA了俩次
首先是一种贪心的思想，题意是要求利用table中给的商品利润和有卖出的期限，计算最大的获利，你可以认为是这样，一个时间只能售出一件商品，但题目中给你的是期限，不是具体哪一天卖出，（我的问题就在这里了），就是把能在期限之前卖出的商品卖出，累加利润，当然，只能在同一天卖出的商品，当然是选择其中利润最大的一件，所以，首先就要对商品的利润进行排序啦，也就是所谓的贪心，首先选择利润最大的，而且最晚卖出，所谓的最晚，就是在最接近期限，而且还没被占用的时间，这里说到了“占用”，也到了并查集出场了
这里关于并查集的应用很巧妙，父节点记录的就是这个所谓的“最接近的期限”啦，对于每一个商品，只要它最接近的期限还未被占用，则可以将其累加进入总利润
这里讲讲如何具体利用并查集实现吧，前面说了，父节点记录的是这个期限之前还没被占用的期限，额，又说到“占用”，首先，因为我们先将商品的利润先排序了嘛，所以没遇到一个商品，只要保证期限之前还有没卖出商品的时间，就可以将这件商品的利润累加，这里，我们利用了数组r[]记录该时间是否卖出商品，未卖出的话，则记录该商品的利润
我们可以想象，用一个连续的区间片段记录一段时间，当然时间是从小到大的，具体的解释还是看代码中的吧，结合代码好理解一些
#include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXN 10010 struct node { int v,d; }ele[MAXN]; int f[MAXN],r[MAXN]; int cmp(const void *a, const void *b) { if(((struct node *)a)->v==((struct node *)b)->v) return ((struct node *)a)->d-((struct node *)b)->d; else return ((struct node *)b)->v-((struct node *)a)->v; } void init(int n)//初始化 { int i; for(i=1;i<=n;i++) { f[i]=i; r[i]=0; } } int find(int x) { if(x==f[x]) return f[x]; f[x]=find(f[x]); return f[x]; }//单纯的查找与路径压缩 int main() { int n,i,sum,t,max; while(scanf("%d",&n)!=EOF) { sum=0;max=0; for(i=0;i<n;i++) { scanf("%d %d",&ele[i].v,&ele[i].d); max=max>ele[i].d?max:ele[i].d; } qsort(ele,n,sizeof(ele[0]),cmp);//按商品利润排序 init(max); for(i=0;i<n;i++) { t=find(ele[i].d);//查找该时间的最近期限 if(t>0) { r[t]=ele[i].v; f[t]=t-1;//这里就是关键所在了，若该时间被占用了，则更新父节点为它的前一个时间点，其他时间点的操作在路径压缩过程中解决 } } for(i=1;i<=max;i++) sum+=r[i];//其实在前面更新节点的时候就可以一边累加了，省去一个循环 printf("%d\n",sum); } return 0; }转载于:https://www.cnblogs.com/nanke/archive/2011/05/09/2041552.html
相关资源：数据结构—成绩单生成器