题目解析
给定n个家族 求出共有几个宗族
输出时 按人均面积降序输出 若有并列 则按成员编号的升序输出
解题思路
应该能见的出是并查集
因为需要找出有几个宗族 所有能说明这个可以往并查集想
既然并查集 且需要排序 那么就需要对象来存储
存什么呢
当前宗族的最小节点
当前宗族的人数
当前宗族的总房产套数
当前宗族的总房产面积
排序呢 就是按照题目的排序即可
因为不确定有多少个节点会被用到 所以一开始就直接设为1e4个
然后呢 用vis去标记是否用过该节点
输入时的 合并节点时 一定要注意 当前节点 的父母以及孩子是否都存在 (可能不存在哦)
然后就是 清点宗族节点的总套房数及总面积
代码
import java.io.*;
import java.util.*;
public class Main
{
static int N = (int) 1e4;
// 存储当前节点祖宗节点
static int fa[] = new int[N + 10];
// 存储当前节点是否被用过
static boolean vis[] = new boolean[N + 10];
// 存储节点信息
static edge shu[] = new edge[N + 10];
static class edge implements Comparable<edge>
{
int id; // 编号
int ren; // 家庭人口
double taofang; // 家庭套房数
double mianji; // 家庭套房总面积
public edge(int id, int ren, double taofang, double mianji)
{
this.id = id;
this.ren = ren;
this.mianji = mianji;
this.taofang = taofang;
}
public String toString()
{
return id + " " + ren + " " + mianji + " " + taofang;
}
@Override
public int compareTo(edge other)
{
double a = this.mianji / this.ren, b = other.mianji / other.ren;
if (a > b)
return -1;
else if (a < b)
return 1;
return this.id - other.id;
}
}
// 寻找祖宗节点
static int find(int x)
{
if (fa[x] != x)
fa[x] = find(fa[x]);
return fa[x];
}
// 合并两个节点 将b划到a的宗谱下
static void merge(int a, int b)
{
vis[a] = vis[b] = true;
int x = find(a), y = find(b);
if (x != y)
fa[y] = x;
}
public static void main(String[] args) throws IOException
{
// 初始化
for (int i = 0; i <= N; i++)
{
fa[i] = i;
shu[i] = new edge(i, 0, 0, 0);
}
int n = sc.nextInt();
while (n-- > 0)
{
int id = sc.nextInt();
// 当前节点需要被用到 因为可能当前节点的父母全部去世了 并且还没有孩子
// 比较不雅的说法 但是有这种情况
vis[id] = true;
int father = sc.nextInt(), mother = sc.nextInt();
// 当前父母没有去世 就合并两个点
if (father != -1) merge(father, id);
if (mother != -1) merge(mother, id);
int soncnt = sc.nextInt();
while (soncnt-- > 0)
{
int son = sc.nextInt();
// 合并当前节点的子节点
merge(id, son);
}
shu[id] = new edge(id, 0, sc.nextInt(), sc.nextInt());
}
for (int i = 0; i <= N; i++)
{
// 当前这个点有被用到 (父母节点 当前节点 子节点)
if (vis[i])
{
// 寻找当前节点的祖宗节点
int u = find(i);
// 当前宗族的编号替换为最小的
shu[u].id = Math.min(shu[u].id, i);
// 当前宗族的人数+1
shu[u].ren++;
// 如果当前的祖宗节点是自己的话 就不需要加上子辈的房屋面积以及套房数
if (u == i) continue;
shu[u].mianji += shu[i].mianji;
shu[u].taofang += shu[i].taofang;
}
}
// 存储当前的宗族
ArrayList<edge> ar = new ArrayList<edge>();
for (int i = 0; i <= N; i++)
{
// 如果当前的宗族有人那么就添加
if (shu[i].ren > 0)
ar.add(shu[i]);
}
// 排序
Collections.sort(ar);
// 输出
out.println(ar.size());
for (edge i : ar)
{
int x = i.ren;
out.printf("%04d %d %.3f %.3f\n", i.id, x, i.taofang / x, i.mianji / x);
}
out.flush();
out.close();
}
static InputReader sc = new InputReader();
static PrintWriter out = new PrintWriter(System.out);
static class InputReader
{
private InputStream inputStream = System.in;
private byte[] buf = new byte[100000];
private int curChar;
private int numChars;
public int getchar()
{
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars)
{
curChar = 0;
try
{
numChars = inputStream.read(buf);
} catch (IOException e)
{
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt()
{
int a = 0, b = 1;
int c = getchar();
while (c < '0' || c > '9')
{
if (c == '-')
{
b = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9')
{
a = (a << 1) + (a << 3) + (c ^ 48);
c = getchar();
}
return a * b;
}
}
}