本文共 2468 字，大约阅读时间需要 8 分钟。

题目描述

This time, you are supposed to help us collect the data for family-owned property. Given each person’s family members, and the estate（房产）info under his/her own name, we need to know the size of each family, and the average area and number of sets of their real estate.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤1000). Then N lines follow, each gives the infomation of a person who owns estate in the format:

ID Father Mother k Child

​1 ​​ ⋯Child ​k ​​ M ​estate ​​ Area

where ID is a unique 4-digit identification number for each person; Father and Mother are the ID’s of this person’s parents (if a parent has passed away, -1 will be given instead); k (0≤k≤5) is the number of children of this person; Child

​i ​​ 's are the ID’s of his/her children; M ​estate ​​ is the total number of sets of the real estate under his/her name; and Area is the total area of his/her estate.

Output Specification:

For each case, first print in a line the number of families (all the people that are related directly or indirectly are considered in the same family). Then output the family info in the format:

ID M AVG

​sets ​​ AVG ​area ​​

where ID is the smallest ID in the family; M is the total number of family members; AVG

​sets ​​ is the average number of sets of their real estate; and AVG ​area ​​ is the average area. The average numbers must be accurate up to 3 decimal places. The families must be given in descending order of their average areas, and in ascending order of the ID’s if there is a tie.

Sample Input:

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 Sample Output: 3 8888 1 1.000 1000.000 0001 15 0.600 100.000 5551 4 0.750 100.000

题意

给出n个人的个人信息，包括自己id，父母id，孩子个数及id，房产数目以及面积，

求每个家族中最小id号以及平均每个人的房产数目和平均面积。按照平均面积降序排序，id升序排序。

思路

对人进行并查集，之后找到每个人的父节点，然后将个人的房产数目和面积加到父节点上。

代码如下

#include 
   
    using namespace std;const int maxn=1e4+5;struct peo{
       int min_id;    int num_st;    int num;    double area;};// 记录每个父节点在v中的位置int vis[maxn];// id 是否存在int is_exist[maxn];// 每个人的房产数目int num_st[maxn];// 每个人的面积double area[maxn];vector
    
      v;bool compare(peo a,peo b){
       double avga=a.area/a.num;    double avgb=b.area/b.num;    if(avga!=avgb) return avga>avgb;    return a.min_id
    
   

转载地址：http://kcaen.baihongyu.com/