题意:给出n个人的id,他父母的id,孩子个数,孩子的id,以及在其名下的房产套数和房产面积。求每个家庭的人数,人均房产套数和人均房产面积,并以该家庭中id最小的那个表示这个家庭。
思路:所谓家庭,就是所有有亲戚关系的人组成的一个集合(如a是b的孩子,而c又是a的孩子...),这在提醒我们应该使用并查集。本题的信息量较多,首先,在输入数据时对id进行合并,这里的Union()函数稍微有点不同,因为题目要求最后输出每个家庭的id是其所有成员中最小的那个,因此在合并时,选择较小值作为两个集合的根(见代码);其次,用exist[id]标记某个id是否出现过,用于后面遍历统计家庭的人数和房产信息。为了不易混淆,本题使用两个结构体来存储信息,一个是Struct Family{...},记录一个家庭的id,总数人,平均房产等信息,用于最后的输出;另一个是Struct Person{...},仅用于读入数据时记录某人的房产信息,在之后的处理中会累加到Family中。接下来开始处理数据,首先遍历0~maxn,统计每个家庭的人数等信息,然后再次遍历,统计家庭个数,最后排序、输出。
代码:
#include#include using namespace std; const int maxn=10005;int exist[maxn]={ 0}; struct Family{ int id,member,totArea,totSets; double avgArea,avgSets; Family(){ id=member=totArea=totSets=0; avgArea=avgSets=0; }}family[maxn];struct Person{ int area,sets; Person():area(0),sets(0){}}p[maxn];int father[maxn];void Init(){ for(int i=0;i b.avgArea; else return a.id