PAT甲级1114.

目录

A1114

题目

样例

输入:

10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100

输出:

3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

思路和坑点

　　思路：
　　此题信息量较大，有一定的的阅读理解难度。题目的输入首先是正整数N，表示将要提供的人员数量。接下里N行，每行包含一个人的个人信息，其中依次包括个人身份编号、父亲编号、母亲编号、孩子个数、对应每个孩子的编号，个人房产套数，个人房产总面积。题目要求的输出结果是，输出家族个数（直系或者旁系的人都算为一个家族，也就是需要合并得到家族并查集），然后每行输出一组家族信息，包括最小成员的编号，家族总人数，平均房产套数，平均房产面积，要求输出的平均值精确到三位小数。
　　主要是需要处理的信息比较多，这里给出的思路是，凡是有关系的人如果还未合并都进行合并统计，统计包括：最小编号、房产等信息，同时还要通过数组保存并查集信息。具体实现见代码。
　　坑点：
　　注意每个信息的含义，以及输出要求。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef struct data{
    int id,fid,mid,num,area;    //记录每一条个人信息，其中包括个人账号id，父母的id，房产套数num，房产面积area
    vector<int> cid;            //孩子数组 
    int minid;                  //minid用于存放此人所在家族中最小的id号
}Data;
typedef struct node{
    int id,people;              //最小id  成员个数 
    double num,area;            //排序和输出的数据 
    bool flag;                  //是否是根 标记 ，初始化为否，如果有家组信息，则改为true 
    node(){
        id=10000; flag=false;   //id初始化为10000也就是最大值，然后和家族中每一条记录比较，如果有更小，则更新 
    }
}Node;
Data all[1005];                 //数据数组 
Node ans[10000];                //答案数组，因为个人编号4位，所以代表可能存在的任务有10000个 
int father[10000];              //并查集father数组，初始化为-1 
int find(int x){                //查找所在编号x所在并查集的父节点
    while(father[x]>=0){
        x=father[x];
    }
    return x;
}
void Union(int a,int b){        //并查集的合并函数
    int fa=find(a);             //找到两个人所在家庭的根
    int fb=find(b);
    if(fa!=fb){                 //如果两人不在同一个家族则进行合并，为了减小并查集路径，将小的合并在大的上边
        if(father[fa]>father[fb]){
            father[fb]+=father[fa];
            father[fa]=fb;
        }
        else{
            father[fa]+=father[fb];
            father[fb]=fa;
        }    
    }
}
bool cmp(Node a,Node b){        //排序函数
    if(a.area!=b.area)        return a.area>b.area;
    else                     return a.id<b.id;
}
int main(){    
#ifdef ONLINE_JUDGE    
#else    
    freopen("1.txt", "r", stdin);    
#endif    
    int n,k,cnt=0;                  //n表示数据个数，k表示每一个人的孩子个数，cnt
    scanf("%d",&n);
    //读入数据并构建并查集关系
    fill(father,father+10000,-1);   //初始化并查集
    for(int i=0;i<n;i++){           //读入数据
        scanf("%d%d%d%d",&all[i].id,&all[i].fid,&all[i].mid,&k);
        all[i].minid=all[i].id;     //暂时初始化每个人所在家庭中最小的id是自己
        if(all[i].fid!=-1){         //如果有父亲，就把自己和父亲所在家族合并
            Union(all[i].id,all[i].fid);
            if(all[i].fid<all[i].minid)     //比较所有亲属的id，将自己的minid更新到最小，凡是遇到亲属就更新，这样每个人都能保证minid是家族中最小的
                all[i].minid=all[i].fid;    //这里更具父亲的id，更新minid
        }
        if(all[i].mid!=-1){         //对母亲采取和父亲同样的处理办法
            Union(all[i].id,all[i].mid);
            if(all[i].mid<all[i].minid)
                all[i].minid=all[i].mid;
        }
        for(int j=0;j<k;j++){       //对儿子也采取和父亲同样的处理办法
            int temp;
            scanf("%d",&temp);      //儿子需要记录在数组中
            all[i].cid.push_back(temp);
            Union(temp,all[i].id);
            if(temp<all[i].minid)
                all[i].minid=temp;
        }
        scanf("%d%d",&all[i].num,&all[i].area); 
    }
    //数据统计计算
    for(int i=0;i<n;i++){           //将每一个人的房产数据统计进入他所在的家庭组 
        int id=find(all[i].id);     //找到所在家族（并查集）的根
        if(all[i].minid<ans[id].id) //用自己小家族的minid更新整个家族的minid
            ans[id].id=all[i].minid; 
        ans[id].num+=all[i].num;    //累加房产套数
        ans[id].area+=all[i].area;  //累加房产面积
        ans[id].flag=true;          //更新标记
    }
    for(int i=0;i<10000;i++){       //遍历答案数组并计算最终的数值
        if(ans[i].flag){            //对于是家族根的更新相关数据
            cnt++;                  //统计家族个数
            ans[i].people=-father[i];//统计家族人数和平均房产数量、平均房产面积
            ans[i].num=(double) (ans[i].num*1.0/ans[i].people);
            ans[i].area=(double)(ans[i].area*1.0/ans[i].people);
        }
    }
    sort(ans,ans+10000,cmp);        //按照规则进行排序
    printf("%d\n",cnt);
    for(int i=0;i<cnt;i++){         //输出最后的结果
        printf("%04d %d %.3f %.3f\n",ans[i].id,ans[i].people,ans[i].num,ans[i].area);
    }
    return 0;    
}