pta l2-7(家庭房产)

2019/03/16 17:40
阅读数 287

题目链接:https://pintia.cn/problem-sets/994805046380707840/problems/994805068539215872

题意:给定n个人的信息,包括其编号,父母以及孩子的编号,以及其名下的房产数量和房产面积,要求有多少个家族,并列出每个家族的最小编号,家庭人数,家庭人均房产数量和人均房产面积。

思路:算法部分就是简单的并查集,但数据处理等方面还挺复杂,一定要仔细。首先用个data结构体数组来存储输入的每个人的信息,用node结构体来存储每个家族的信息,其中包括该家族最小成员编号,人数,人均房产数量和人均房产面积,其中flag涌来标识是否存在,因为数据量不大,可以暴力处理,就是要注意编码细节。输入人的信息时,将他和其父母孩子合并,并使祖先的编号最小,用vis数组标记该编号是否出现。合并之后遍历n个人,将其1房产信息都加入到家族结构体中,最后还要排序,先按人均房产面积降序排列,再按编号升序排列。

AC代码:

#include<bits/stdc++.h>
using namespace std;

struct data{
    int id,fa,ma,k,num,area;
    int ch[6];
}a[1005];

struct node{
    int idm,pp,flag;
    double num,area;
}fam[10005];

int root[10005],vis[10005],n,res;

int getr(int k){
    if(root[k]==k) return k;
    else return root[k]=getr(root[k]);
}

void Union(int x,int y){
    int xr=getr(x),yr=getr(y);
    if(xr<yr)
        root[yr]=xr;
    else
        root[xr]=yr;
}

bool cmp(node xx,node yy){
    if(xx.area==yy.area)
        return xx.idm<yy.idm;
    else
        return xx.area>yy.area;
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<10000;++i)
        root[i]=i;
    for(int i=0;i<n;++i){
        scanf("%d%d%d%d",&a[i].id,&a[i].fa,&a[i].ma,&a[i].k);
        for(int j=0;j<a[i].k;++j)
            scanf("%d",&a[i].ch[j]);
        scanf("%d%d",&a[i].num,&a[i].area);
        vis[a[i].id]=1;
        if(a[i].fa!=-1)
            vis[a[i].fa]=1,Union(a[i].id,a[i].fa);
        if(a[i].ma!=-1)
            vis[a[i].ma]=1,Union(a[i].id,a[i].ma);
        for(int j=0;j<a[i].k;++j)
            vis[a[i].ch[j]]=1,Union(a[i].id,a[i].ch[j]);
    }    
    for(int i=0;i<n;++i){
        int idr=getr(a[i].id);
        fam[idr].idm=idr;
        fam[idr].num+=a[i].num;
        fam[idr].area+=a[i].area;
        fam[idr].flag=1;
    }
    for(int i=0;i<10000;++i){
        if(vis[i]) ++fam[getr(i)].pp;
        if(fam[i].flag) ++res;
    }
    for(int i=0;i<10000;++i)
        if(fam[i].flag){
            fam[i].num=fam[i].num*1.0/(fam[i].pp*1.0);
            fam[i].area=fam[i].area*1.0/(fam[i].pp*1.0);
        }
    sort(fam,fam+10000,cmp);
    printf("%d\n",res);
    for(int i=0;i<res;++i)
        printf("%04d %d %.3f %.3f\n",fam[i].idm,fam[i].pp,fam[i].num,fam[i].area);
    return 0;
}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部