PTA题目

题目"/>

PTA题目

给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。

输入格式：

输入第一行给出一个正整数N（≤1000），随后N行，每行按下列格式给出一个人的房产：

编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积

其中编号是每个人独有的一个4位数的编号；父和母分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（0≤k≤5）是该人的子女的个数；孩子i是其子女的编号。

输出格式：

首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：

家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积

其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。

输入样例：

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

 解题代码：（代码来源：）

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std ;
#define MAX 10005
int p[MAX],visit[MAX]={0},la[MAX]={0};
struct node
{int id , people ;double sum , num ;
};
node person[MAX] ,ans[MAX],p2[MAX];
bool comp(const struct node&a,const struct node&b)
{if(a.sum == b.sum)return a.id < b.id;return a.sum > b.sum;
}
int Find(int x)
{int temp = x ;while(p[temp]!=temp)temp = p[temp] ;return temp;
}
void join(int x , int y)
{int t1 , t2 ;t1 = Find(x) ;t2 = Find(y) ;if(t1 != t2){if(t1 > t2){p[t1] = t2 ;}else p[t2] = t1 ;}
}
int main()
{int n ,id, nm , nf , k , nk;double hn , hs;scanf("%d" , &n);for(int i = 0 ; i <MAX ; i ++){p[i] = i ;}for(int i = 0 ; i <n ; i ++){scanf("%d%d%d",&id,&nf,&nm);visit[id] = 1 ;if(nm!=-1) {join(id,nm);visit[nm]=1;}if(nf!=-1) {join(id,nf);visit[nf]=1;}scanf("%d",&k);for(int i = 0 ; i < k ; i ++){scanf("%d" , &nk);if(nk!=-1){join(id,nk);visit[nk] = 1;}}scanf("%lf%lf",&person[i].num,&person[i].sum);person[i].id = id;}for(int i = 0 ; i < n ; i ++){int tid = Find(person[i].id);p2[tid].id = tid;p2[tid].num += person[i].num;p2[tid].sum += person[i].sum;//cout << p2[tid].sum<<endl;}int ren = 0 ;for(int i = 0 ; i < MAX ; i ++){if(visit[i])p2[Find(i)].people++;}for(int i = 0 ; i <MAX ; i ++){if(visit[i]){int ttt = Find(i) ;if(!la[ttt]){la[ttt] = 1 ;//cout <<p2[ttt].num<<endl;double xx = double(p2[ttt].people);ans[ren].id = ttt;ans[ren].num = p2[ttt].num*1.0/xx;ans[ren].sum = p2[ttt].sum*1.0/xx;ans[ren++].people = int(xx) ;}}}printf("%d\n" , ren) ;sort(ans,ans+ren,comp);for(int i = 0 ; i < ren ; i ++)printf("%04d %d %.3f %.3f\n" , ans[i].id,ans[i].people,ans[i].num,ans[i].sum);return 0 ;
}

代码解析：

题目首先想到的就是并查集，意思就是让你把一家一家又一家的人合并成大家族，之后统计整个家族的房产信息。
解题分为以下几个过程：

1.使用并查集是合并输入id的父母及子女信息

2.计算一个大家族的房产总数

3.通过一个visit数组及查询函数统计家庭总人数

4.组合运算