当前位置:网站首页>L2-007 family real estate (25 points)
L2-007 family real estate (25 points)
2022-07-06 11:26:00 【%xiao Q】
subject
Give everyone's family members and their own properties , Please count the population of each family 、 Per capita real estate area and number of real estate units .
Input format :
The first line of input gives a positive integer N(≤1000), And then N That's ok , Each line gives a person's property in the following format :
Number Father mother k children 1 … children k Number of real estate units Total area
The number is unique to everyone 4 Number of digits ; The parent and the parent are the number of the parent corresponding to the number ( If you have passed away , Is displayed -1);k(0≤k≤5) It's the number of children of the person ; children i Is the number of their child .
Output format :
First, output the number of families in the first line ( All relatives belong to the same family ). Then output the information of each family in the following format :
Minimum number of family members The number of families Per capita number of real estate units Per capita real estate area
The per capita value shall be kept after the decimal point 3 position . Family information is first output in descending order of per capita area , If there is juxtaposition , Then output... In ascending order of member number .
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
analysis
A problem of parallel search set , See code for details !!!
Reference code :
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++)
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;
const int N = 1010, M = 1e4;
int n;
bool st[M]; // Mark those id There have been
int p[M];
struct data
{
int id, num, area;
}a[N];
struct stu
{
int id, people;
double num, area;
bool flag;
}ans[M];
// Find the parent node
int find(int x)
{
while(x != p[x]) x = p[x];
return x;
}
// Merge 2 Subtree
void Union(int x, int y)
{
int fx = find(x);
int fy = find(y);
if(fx > fy) p[fx] = fy;
else p[fy] = fx;
}
bool cmp(stu x, stu y)
{
if(x.area != y.area) return x.area > y.area;
return x.id < y.id;
}
int main()
{
cin >> n;
rep(i, 0, M) p[i] = i; // Initialize the parent node of all points for itself
rep(i, 1, n)
{
int id, d_id, m_id, k, son, num, area;
cin >> id >> d_id >> m_id;
st[id] = true;
if(d_id != -1)
{
st[d_id] = true;
Union(id, d_id);
}
if(m_id != -1)
{
st[m_id] = true;
Union(id, m_id);
}
cin >> k;
while(k--)
{
cin >> son;
st[son] = true;
Union(id, son);
}
cin >> num >> area;
a[i] = {
id, num, area};
}
rep(i, 1, n)
{
int id = find(a[i].id);
ans[id].id = id;
ans[id].num += a[i].num;
ans[id].area += a[i].area;
ans[id].flag = true; // Number of marked families
}
int cnt = 0;
// because id The data range is small , Directly enumerate all possible 4 number id, And use the fear and search set to accumulate the family population
rep(i, 0, 9999)
{
if(st[i]) ans[find(i)].people++;
if(ans[i].flag) cnt++;
}
rep(i, 0, 9999)
if(ans[i].flag)
{
ans[i].num = ans[i].num / ans[i].people;
ans[i].area = ans[i].area / ans[i].people;
}
sort(ans, ans + M, cmp);
cout << cnt << endl;
// Because it is output in descending order according to the average area , So you can output directly after sorting
rep(i, 0, cnt - 1)
printf("%04d %d %.3f %.3f\n", ans[i].id, ans[i].people, ans[i].num, ans[i].area);
return 0;
}
边栏推荐
猜你喜欢
Image recognition - pyteseract TesseractNotFoundError: tesseract is not installed or it‘s not in your path
Unable to call numpy in pycharm, with an error modulenotfounderror: no module named 'numpy‘
QT creator specifies dependencies
[Blue Bridge Cup 2017 preliminary] grid division
基于apache-jena的知识问答
How to configure flymcu (STM32 serial port download software) is shown in super detail
[download app for free]ineukernel OCR image data recognition and acquisition principle and product application
Rhcsa certification exam exercise (configured on the first host)
一键提取pdf中的表格
Reading BMP file with C language
随机推荐
MTCNN人脸检测
Base de données Advanced Learning Notes - - SQL statements
Test objects involved in safety test
Face recognition_ recognition
Software testing and quality learning notes 3 -- white box testing
yarn安装与使用
QT creator specify editor settings
How to configure flymcu (STM32 serial port download software) is shown in super detail
Ansible practical series I_ introduction
保姆级出题教程
Solution of deleting path variable by mistake
Case analysis of data inconsistency caused by Pt OSC table change
[蓝桥杯2017初赛]方格分割
Armv8-a programming guide MMU (2)
数数字游戏
AI benchmark V5 ranking
图片上色项目 —— Deoldify
Remember a company interview question: merge ordered arrays
学习问题1:127.0.0.1拒绝了我们的访问
Why can't STM32 download the program