Supermarket【并查集】【贪心】

贪心】"/>

Supermarket【并查集】【贪心】

>Description
有一个商店有许多批货，每一批货又有N(0<=N<=10^4104 )个商品,同时每一样商品都有收益PiP_iPi​ ,和过期时间DiD_iDi​ (1<=Pi,DiPi,DiPi,Di <=10^4104 )，一旦超过了过期时间，商品就不能再卖。

你要做的就是求出每批货最多能得到多少收益。

>Input
多组数据，每组先给出一个整数N，表示这批货的商品个数。

然后有N对数，每对数有两个用空格隔开的正整数Pi,DiP_i,D_iPi​,Di​ ,表示第i个商品的收益和过期时间。相邻两对数之间用空格隔开。

输入以一个文件终止符结束，并且保证所有输入数据正确。

>Output
对于每组数据，输出一行一个整数表示该批货物能卖出的最大价格。

>Sample Input
4 50 2 10 1 20 2 30 1
7 20 1 2 1 10 3 100 2 8 2 5 20 50 10

>Sample Output
80
185

>解题思路
并查集+贪心。
按照价值从大到小排序，也就是先卖价格最大的；看看当前商品能最晚卖出的时间，那时候是不是已经有商品卖，如果没有，就直接在那个时间卖掉，如果有，就把时间往前推。

>代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct ooo
{int c,t;
}a[100005];
int n,cc[100005],ans,tt;
bool lil(ooo aa,ooo bb)
{if(aa.c!=bb.c) return aa.c>bb.c;else return aa.t>bb.t;
}
int find(int v)
{if(cc[v]==v) return v;return cc[v]=find(cc[v]);
}
void work()
{ans=0;for(int i=1;i<=100000;i++)cc[i]=i;for(int i=1;i<=n;i++)scanf("%d%d",&a[i].c,&a[i].t);sort(a+1,a+1+n,lil);for(int i=1;i<=n;i++){tt=find(a[i].t);if(tt!=0) //如果有时间可以卖出{cc[tt]=tt-1;ans+=a[i].c; //直接加上价值}}printf("%d\n",ans);
}
int main()
{while(scanf("%d",&n)==1) work();return 0;
}