pku1456(Supermarket)

it2022-05-06  4

悲剧呀,我怎么又理解错题意了,写了一个代码,固执的修改提交,都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

相关资源:数据结构—成绩单生成器

最新回复(0)