By Jalan
文章目录
**By Jalan**知识工具需求数学数据结构和算法语言
题干输入条件输出条件例子例1输入输出
题解第一次思路预期时间复杂度编写用时代码CPP运行用时
结尾
知识工具需求
数学
数据结构和算法
并查集
语言
题干
统计真实的财富(人均空间?)
输入条件
N<=1000 下面N行每行是 ID Father Mother k Childik Mestate Area 这个格式 ID4位,过世的用-1代替 k>=0<=5是孩子个数
输出条件
家庭个数 ID M AVGsets AVGarea id是家族里id最小的人的id M人数 AVG3位小数 AVGarea降序,tie则id升序.
例子
例1
输入
输出
题解
第一次
思路
并查集问题,这里的边指的就是血缘关系.就是出现在同一行.
输入到list里遍历list进行union完成建立并查集树之后遍历list的id找根节点使用map结构体counter进行统计.由于要统计人数可能会出现重复的情况,这里还需要一个vis进行辅助把map结果输出到ans数组,排序数组输出
预期时间复杂度
编写用时
40分钟
代码
CPP
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdio>
#include <map>
#include <stdio.h>
#include <unordered_map>
#include <vector>
using namespace std
;
const int notFound
= -1;
typedef struct node
{
int id
;
int fid
;
int mid
;
int k
;
int childId
[6];
int set
;
int area
;
} node
;
int n
;
int findRoot(int x
, vector
<int> &parent
)
{
while (parent
[x
] != x
)
{
x
= parent
[x
];
}
return x
;
}
int unionNode(int x
, int y
, vector
<int> &parent
)
{
int xr
= findRoot(x
, parent
);
int yr
= findRoot(y
, parent
);
if (xr
< yr
)
{
parent
[yr
] = xr
;
}
else
{
parent
[xr
] = yr
;
}
return 1;
}
typedef struct counter
{
int set
;
int area
;
int people
;
int root
;
double avga
;
double avgs
;
} counter
;
vector
<int> vis(10001);
bool cmp(counter a
, counter b
)
{
if (a
.avga
> b
.avga
)
{
return true;
}
else if (a
.avga
== b
.avga
)
{
if (a
.root
< b
.root
)
{
return true;
}
}
return false;
}
int main(int argc
, char const *argv
[])
{
scanf("%d", &n
);
vector
<node
> list(n
);
for (int i
= 0; i
< n
; i
++)
{
scanf("%d%d%d%d", &list
[i
].id
, &list
[i
].fid
, &list
[i
].mid
, &list
[i
].k
);
for (int j
= 0; j
< list
[i
].k
; j
++)
{
scanf("%d", &list
[i
].childId
[j
]);
}
scanf("%d%d", &list
[i
].set
, &list
[i
].area
);
}
vector
<int> parent(10001);
for (int i
= 0; i
< 10001; i
++)
{
parent
[i
] = i
;
}
for (int i
= 0; i
< n
; i
++)
{
if (list
[i
].fid
!= -1)
{
unionNode(list
[i
].id
, list
[i
].fid
, parent
);
}
if (list
[i
].mid
!= -1)
{
unionNode(list
[i
].id
, list
[i
].mid
, parent
);
}
for (int j
= 0; j
< list
[i
].k
; j
++)
{
unionNode(list
[i
].id
, list
[i
].childId
[j
], parent
);
}
}
unordered_map
<int, counter
> m
;
for (int i
= 0; i
< n
; i
++)
{
int root
= findRoot(list
[i
].id
, parent
);
if (list
[i
].id
!= -1 && vis
[list
[i
].id
] == 0)
{
m
[root
].people
++;
vis
[list
[i
].id
] = 1;
}
if (list
[i
].fid
!= -1 && vis
[list
[i
].fid
] == 0)
{
m
[root
].people
++;
vis
[list
[i
].fid
] = 1;
}
if (list
[i
].mid
!= -1 && vis
[list
[i
].mid
] == 0)
{
m
[root
].people
++;
vis
[list
[i
].mid
] = 1;
}
for (int j
= 0; j
< list
[i
].k
; j
++)
{
if (vis
[list
[i
].childId
[j
]] == 0)
{
m
[root
].people
++;
vis
[list
[i
].childId
[j
]] = 1;
}
}
m
[root
].area
+= list
[i
].area
;
m
[root
].set
+= list
[i
].set
;
}
vector
<counter
> ans
;
for (auto &&i
: m
)
{
i
.second
.root
= i
.first
;
i
.second
.avga
= (double)i
.second
.area
/ i
.second
.people
;
i
.second
.avgs
= (double)i
.second
.set
/ i
.second
.people
;
ans
.push_back(i
.second
);
}
sort(ans
.begin(), ans
.end(), cmp
);
printf("%d\n",ans
.size());
for (int i
= 0; i
< ans
.size(); i
++)
{
printf("d %d %0.3lf %0.3lf\n",ans
[i
].root
,ans
[i
].people
,ans
[i
].avgs
,ans
[i
].avga
);
}
return 0;
}
运行用时
结尾
看在我写了这么多注释的份上可以给我点个赞嘛,求求惹=]砰砰砰,给我加点写下去的油呀@.@ 也欢迎关注我的账号呀,接下来两个月我应该会按这个格式更新所有的PTA甲级题目
**开心code每一天**
