PTA 天梯赛备赛 L2-007 家庭房产 (25分)(并查集+结构体排序)
发布日期:2021-06-29 14:35:10
浏览次数:2
分类:技术文章
本文共 2089 字,大约阅读时间需要 6 分钟。
题目描述
给定每个人的家庭成员和其自己名下的房产,请你统计出每个家庭的人口数、人均房产面积及房产套数。
输入格式:
输入第一行给出一个正整数N(≤1000),随后N行,每行按下列格式给出一个人的房产:编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积
其中编号是每个人独有的一个4位数的编号;父和母分别是该编号对应的这个人的父母的编号(如果已经过世,则显示-1);k(0≤k≤5)是该人的子女的个数;孩子i是其子女的编号。
输出格式:
首先在第一行输出家庭个数(所有有亲属关系的人都属于同一个家庭)。随后按下列格式输出每个家庭的信息:家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积
其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出,若有并列,则按成员编号的升序输出。输入样例:
106666 5551 5552 1 7777 1 1001234 5678 9012 1 0002 2 3008888 -1 -1 0 1 10002468 0001 0004 1 2222 1 5007777 6666 -1 0 2 3003721 -1 -1 1 2333 2 1509012 -1 -1 3 1236 1235 1234 1 1001235 5678 9012 0 1 502222 1236 2468 2 6661 6662 1 3002333 -1 3721 3 6661 6662 6663 1 100
输出样例:
38888 1 1.000 1000.0000001 15 0.600 100.0005551 4 0.750 100.000
解题思路
并查集+结构体排序。
…这个排序挺难搞的。通过 vis
判断当前用户编号是否存在,然后通过并查集,将属于同一个家庭的人连接在一起。其次,统计一个家庭中人的数量,求出人均房产套数和人均房产面积。
最后,通过结构体排序得到我们最后想要的结果。
提交代码
#includeusing namespace std;const int maxn=1e4+5;struct DATA { int id,fid,mid,num,area; int cid[10];}data[maxn];struct node{ int id,people; double num,area; bool flag=false;}stu[maxn];int father[maxn];bool vis[maxn];// 并查集int findFather(int x){ if(x!=father[x]) father[x] = findFather(father[x]); return father[x];}void join(int a,int b){ int fa = findFather(a); int fb = findFather(b); if(fa > fb) father[fa] = fb; else if(fa < fb) father[fb] = fa;}// 排序比较函数int cmp(node x,node y){ if(x.area != y.area) return x.area > y.area; else return x.id < y.id;}int main(){ int n,k; cin>>n; for(int i=0;i >data[i].id>>data[i].fid>>data[i].mid>>k; vis[data[i].id] = true; // if(data[i].fid != -1){ vis[data[i].fid] = true; join(data[i].fid, data[i].id); } if(data[i].mid != -1){ vis[data[i].mid] = true; join(data[i].mid, data[i].id); } for(int j=0;j >data[i].cid[j]; vis[data[i].cid[j]] = true; join(data[i].cid[j],data[i].id); } cin>>data[i].num>>data[i].area; } for(int i=0;i
学如逆水行舟,不进则退
转载地址:https://chocolate.blog.csdn.net/article/details/110007786 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月12日 03时35分29秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
爬取小说——爬取书的地址
2019-04-29
爬取小说——爬取章节地址
2019-04-29
爬取小说——爬取标题和正文
2019-04-29
爬取小说——储存为TXT格式
2019-04-29
爬取小说——主体部分
2019-04-29
Python 窗口化操作
2019-04-29
excel的常用函数(二)
2019-04-29
excel的逻辑函数
2019-04-29
excel文本函数
2019-04-29
excel时间日期函数
2019-04-29
power BI desktop
2019-04-29
中国信息化发展八大趋势(一)
2019-04-29
中国信息化发展八大趋势(二)
2019-04-29
中国信息化发展八大趋势(三)
2019-04-29
中国信息化发展八大趋势(四)
2019-04-29
电商大战二十年
2019-04-29
编程程软件测试思维方式:如何科学制定测试计划
2019-04-29
BLE蓝牙4.0串口调试助手
2019-04-29
树莓派WIFI设置
2019-04-29