PAT-L2-007-gplt真题

Cwolf9 2018-03-26 原文

PAT-L2-007-gplt真题

题目分析：

1. 首先，题目说一个家庭有孩子爸爸妈妈等几辈人，可以利用并查集将一个家庭里的所有人变成一个集合；

2. 刚好题目的目的也是这样，输出的是一个家庭人数，人均房产面积，人均房产套数等；

3. 然后每个家庭保留最小的id，这步在并查集Union时可以实现；

4. 并查集合并后，每个家庭只有一个id，就是最小的那个id；

5. 然后将新的集合处理一下输出就好了；

链接：https://www.patest.cn/contests/gplt/L2-007

(怎么添加链接？？）

（csdn和博客园要是能同步就好了）(逃

AC代码如下：

#include<bits/stdc++.h>  
#define test printf("***\n")  
#define iis std::ios::sync_with_stdio(false)  
using namespace std;  
typedef long long LL;  
const int N = 11000;  
const int M = 1000005;  
const int INF = 0x3f3f3f3f;  
const LL mod = 1000000007;  
const double eps=1e-8;  
struct lp{  
    double ans1,ans2;//ans1是房产套数,ans2是房产面积  
    int id,num;  
    lp(){ans1=ans2=num=id=0;}  
    friend bool operator <(const lp &A,const lp &B){  
        if(A.ans2!=B.ans2)return A.ans2>B.ans2;  
        return A.id<B.id;  
    }  
}a[N],b[N],mul[N];//a是初始，mul是并查集处理后的，b是答案  
int vis[N],m[N],fa[N];//m数组记录的是家庭id，和vis一个作用  
int n;  
void init(){//初始化  
    for(int i=0;i<N;++i)fa[i]=i;  
    memset(vis,0,sizeof(vis));  
    memset(m,0,sizeof(m));  
}  
int Fi(int x){  
    return fa[x]==x?x:fa[x]=Fi(fa[x]);  
}  
void un(int a,int b){//union这里的小细节，是每个家庭只保留最小id  
    int x=Fi(a),y=Fi(b);  
    if(x==y)return;  
    if(x>y)fa[x]=y;  
    else fa[y]=x;  
}  
int main(){  
    scanf("%d",&n);  
    init();  
    for(int i=0;i<n;++i){  
        int p1,p2,d,k;  
        scanf("%d%d%d",&a[i].id,&p1,&p2);  
        vis[a[i].id]=1;  
        if(p1!=-1){  
            un(p1,a[i].id);  
            vis[p1]=1;  
        }  
        if(p2!=-1){  
            un(p2,a[i].id);  
            vis[p2]=1;  
        }  
        scanf("%d",&k);  
        while(k--){  
            scanf("%d",&d);  
            if(d!=-1){  
                un(a[i].id,d);  
                vis[d]=1;  
            }  
        }  
        double aa,bb;  
        scanf("%lf %lf",&aa,&bb);  
        a[i].ans1=aa;a[i].ans2=bb;  
    }  
    for(int i=0;i<n;++i){//合并家庭  
        int id=Fi(a[i].id);  
        mul[id].id=id;  
        mul[id].ans1+=a[i].ans1;  
        mul[id].ans2+=a[i].ans2;  
    }  
    for(int i=0;i<10000;++i){  
        if(vis[i]){  
            mul[Fi(i)].num++;  
        }  
    }  
    int k=0;  
    for(int i=0;i<10000;++i){  
        if(vis[i]){  
            int id=Fi(i);  
            if(!m[id]){  
                m[id]=1;  
                double x=mul[id].ans2/mul[id].num;  
                b[k].ans2=x;  
                b[k].id=id;  
                x=mul[id].ans1/mul[id].num;  
                b[k].num=mul[id].num;  
                b[k++].ans1=x;  
            }  
        }  
    }  
    sort(b,b+k);  
    printf("%d\n",k);//这里要输出家庭总数  
    for(int i=0;i<k;++i){  
        printf("%04d %d %.3f %.3f\n",b[i].id,b[i].num,b[i].ans1,b[i].ans2);  
    }  
    return 0;  
}