145. 超市 AcWing
考察：并查集+贪心或堆排序+贪心
因为最近在做并查集专题所以直接考虑用并查集写,但是看题目完全没有想到用并查集的方式,以前写的并查集题目关系的传递性都很明显,但是这道题本蒟蒻完全没看出来
思路：
用并查集维护天数,贪心策略是能多晚卖出就多晚卖出,起初每个天数都在它自己的集合里,当我们决定要卖出此商品时(设过期天数为d),那么第d个位置就被占用了,我们需要让d这个位置指向在它前面第一个空闲的位置.因为是和它前面的链接,所以直接链接d与d-1即可.当所指的位置到0,那么说明这个商品不能被卖出,利用路径压缩可以把时间复杂度压到O(1)
1 #include2 #include 3 using namespace std; 4 typedef pair<int,int> pii; 5 const int N = 10010; 6 int p[N]; 7 pii goods[N]; 8 struct cmp{//按价值排序 9 bool operator()(pii x,pii y){ 10 return x.first>y.first; 11 } 12 }; 13 int find(int x) 14 { 15 if(x!=p[x]) p[x] = find(p[x]); 16 return p[x]; 17 } 18 int main() 19 { 20 int t; 21 while(scanf("%d",&t)!=EOF){ 22 fill(p,p+N,0); int ans = 0; 23 for(int i=1;i<=t;i++) scanf("%d%d",&goods[i].first,&goods[i].second); 24 for(int i=1;i<=N-10;i++) p[i] = i; 25 sort(goods+1,goods+t+1,cmp()); 26 for(int i=1;i<=t;i++){ 27 int px = find(goods[i].second); 28 if(px){ 29 ans+=goods[i].first; 30 p[px] = find(px-1); 31 } 32 } 33 printf("%d\n",ans); 34 } 35 return 0; 36 }
每天在orz算法竞赛进阶指南....
原文：https://www.cnblogs.com/newblg/p/14227132.html