PTA 天梯赛备赛 L2-007 家庭房产 (25分)(并查集+结构体排序)
发布日期:2021-06-29 14:35:10
浏览次数:3
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月22日 04时19分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
只看到了别人28岁退休,背后的期权知识你知道吗?
2019-04-29
怒肝两个月MySQL源码,我总结出这篇2W字的MySQL协议详解(超硬核干货)!!
2019-04-29
1.5w字,30图带你彻底掌握 AQS!
2019-04-29
硬核!15张图解Redis为什么这么快
2019-04-29
如何无侵入管理所有的微服务接口?
2019-04-29
我的第一份工作是个小公司
2019-04-29
分布式一致性算法-Paxos、Raft、ZAB、Gossip
2019-04-29
一个技术总监的忠告:精通那么多技术,你为何还是受不到重用?
2019-04-29
【高并发】面试官问我:为啥局部变量是线程安全的?
2019-04-29
进阶必看的 RocketMQ ,就这篇了
2019-04-29
拼多多员工爆料:拼多多开启硬核模式!午休减半!每月工作300小时!千万别来拼多多!...
2019-04-29
要我说,多线程事务它必须就是个伪命题!
2019-04-29
丢人不!还用System.out.println("");太 Low了!
2019-04-29
实战篇:一个核心系统 3 万多行代码的重构之旅
2019-04-29
刨根问底,Kafka消息中间件到底会不会丢消息
2019-04-29
破4!《我想进大厂》之Java基础夺命连环16问
2019-04-29
五分钟看懂抓包神技:DPDK
2019-04-29