poj1456 Supermarket[另类的并查集做法]

1.Supermarket(题目地址)

跟很久以前模拟的打地鼠那题一样，贪心+优先队列。这次换用并查集做法。

还是基于贪心，但这次换一种策略，先选价值最大的，

同时使其尽可能晚的被选上（因为早选会将之前可选的日子占用，很显然）。

将并查集f[i]表示从第i天往前看最晚的空下来的一天。

初始时还是每个点（即每天）指向自己，选物品时从这天开始找father，即之前我们维护的东西。

找到后将祖先指向上一个集合中（可以脑袋里面想象一下），累计答案。

如果祖先为0，代表没有可选的日子了（想一想为什么）。

平常见到的都是极裸的disjoint-set，这种变形应当学会构造...

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<vector>
 8 #define dbg(x) cerr<<#x<<" = "<<x<<endl
 9 #define ddbg(x,y) cerr<<#x<<" = "<<x<<"   "<<#y<<" = "<<y<<endl
10 using namespace std;
11 typedef long long ll;
12 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;}
13 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;}
14 template<typename T>inline T _min(T A,T B){return A<B?A:B;}
15 template<typename T>inline T _max(T A,T B){return A>B?A:B;}
16 template<typename T>inline T read(T&x){
17     x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
18     while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
19 }
20 const int N=10000+7;
21 struct thx{
22     int tim,val;
23     inline bool operator <(const thx&A)const{
24         return val>A.val;
25     }
26 }a[N];
27 int fa[N],maxt,n,ans;
28 inline int Get(int x){return fa[x]^x?fa[x]=Get(fa[x]):x;}
29 
30 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);
31     while(~scanf("%d",&n)){ans=maxt=0;
32         for(register int i=1;i<=n;++i)read(a[i].val),MAX(maxt,read(a[i].tim));
33         for(register int i=1;i<=maxt;++i)fa[i]=i;
34         sort(a+1,a+n+1);
35         for(register int i=1;i<=n;++i){
36             int x=Get(a[i].tim);
37             if(x)ans+=a[i].val,fa[x]=Get(x-1);
38         }
39         printf("%d
",ans);
40     }
41     return 0;
42 }