L2-007 家庭房产(Java)

2024-03-26数据结构与算法6 分钟139 次阅读
AI 摘要salmon-ai

本文详细解析了 PAT L2-007“家庭房产”这道题的并查集解法:先

问题

给定每个人的家庭成员和其自己名下的房产,请你统计出每个家庭的人口数、人均房产面积及房产套数。

输入格式:
输入第一行给出一个正整数N(≤1000){N(\leq1000)},随后N{N}行,每行按下列格式给出一个人的房产:

sh 复制代码
编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积

其中编号是每个人独有的一个4位数的编号;父和母分别是该编号对应的这个人的父母的编号(如果已经过世,则显示-1);k(0≤k≤5){(0\leq k\leq5)}是该人的子女的个数;孩子i是其子女的编号。

输出格式:
首先在第一行输出家庭个数(所有有亲属关系的人都属于同一个家庭)。随后按下列格式输出每个家庭的信息:

sh 复制代码
家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积

其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出,若有并列,则按成员编号的升序输出。

输入样例:

sh 复制代码
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

输出样例:

sh 复制代码
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000
sh 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB

题解

该题其实就是一道并查集问题,这里使用一个data来存储数据,用vis标记已经出现的编号,并用parent来标记每个编号的根节点。

代码实现:

java 复制代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

// L2-007 家庭房产
public class Main {
	private static int[] parent = new int[10001]; // 记录对应编号的根节点
	private static boolean[] vis = new boolean[10001]; // 用来标记输入时所有出现的编号

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// 按照编号存储
		Node[] node = new Node[10001];
		// 并查集:初始化
		for (int i = 0; i < 10001; i++) {
			parent[i] = i;
			node[i] = new Node();
		}
		int n = Integer.parseInt(br.readLine());
		Data[] data = new Data[n];

		for (int i = 0; i < n; i++) {
			// 编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积
			String str = br.readLine();
			String[] arr = str.split(" ");
			data[i] = new Data();
			data[i].id = Integer.parseInt(arr[0]);
			data[i].fid = Integer.parseInt(arr[1]);
			data[i].mid = Integer.parseInt(arr[2]);
			data[i].k = Integer.parseInt(arr[3]);

			// 标记已经处理过的编号
			vis[data[i].id] = true;

			// 把父母融入到一个大集合中
			if (data[i].fid != -1) {
				vis[data[i].fid] = true; // 标记已经处理过的编号
				union(data[i].id, data[i].fid);
			}
			if (data[i].mid != -1) {
				vis[data[i].mid] = true; // 标记已经处理过的编号
				union(data[i].id, data[i].mid);
			}

			// 处理孩子
			for (int j = 0; j < data[i].k; j++) {
				data[i].cid[j] = Integer.parseInt(arr[j + 4]);
				vis[data[i].cid[j]] = true; // 标记已经处理过的编号
				union(data[i].id, data[i].cid[j]);
			}

			data[i].house = Integer.parseInt(arr[arr.length - 2]);
			data[i].area = Integer.parseInt(arr[arr.length - 1]);
		}

		// 先记录最小编号,累加房产套数 面积
		for (int i = 0; i < n; i++) {
			int root = find(data[i].id); // 找到当前编号的根节点
			node[root].flag = true; // 在树的根节点标记是一个大家庭
			node[root].avgHouse += data[i].house; // 人均房产套数
			node[root].minNum = root; // 家庭成员的最小编号
			node[root].avgArea += data[i].area; // 人均房产面积
		}

		// 累加家庭成员
		int family_count = 0;
		for (int i = 0; i < 10001; i++) {
			if (vis[i]) {
				int root = find(i);
				node[root].count++; // 计算每个大家庭总人数
			}
			if (node[i].flag) {
				family_count++; // 计算有几个大家庭
			}
		}

		// 算人均房产套数 人均房产面积
		for (int i = 0; i < 10001; i++) {
			if (node[i].flag) {
				node[i].avgHouse = node[i].avgHouse * 1.0 / node[i].count;
				node[i].avgArea = node[i].avgArea * 1.0 / node[i].count;
			}
		}

		// 排序
		Arrays.sort(node);

		System.out.println(family_count);
		for (int i = 0; i < family_count; i++) {
			// 家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积
			System.out.printf("%04d %d %.3f %.3f\n", node[i].minNum, node[i].count, node[i].avgHouse, node[i].avgArea);
		}
	}

	// 合并
	private static void union(int id, int cid) {
		// 找到这两个编号所在树中的根节点
		int ra = find(id);
		int rb = find(cid);

		// 让最小的编号作为根节点
		if (ra > rb) {
			parent[ra] = rb;
		} else {
			parent[rb] = ra;
		}
	}

	// 查找
	private static int find(int id) {
		int root = id;
		// 循环找到当前数的根节点,即根节点的 parent 指向自己
		// 这样做的目的是找到元素 id 所在的集合的根节点
		while (parent[root] != root) {
			// 获取当前结点的根编号
			root = parent[root];
		}
		// 压缩路径,减少树的层数,防止树的退化。
		// 将 x 到根节点的路径上的所有节点直接连接到根节点上,从而减少树的深度
		while (parent[id] != root) {
			int temp = parent[id]; // 拿到当前节点的根节点编号
			parent[id] = root; // 连接到新的根节点
			id = temp; // 继续处理下一个节点
		}
		return root;
	}

}

class Data {
	int id; // 当前编号
	int fid, mid; // 父母编号
	int k, house, area;
	int[] cid = new int[10]; // 家庭
}

class Node implements Comparable<Node> {
	int minNum; // 家庭最小编号
	int count; // 家庭人口数
	double avgHouse; // 人均房产套数
	double avgArea; // 人均房产面积
	boolean flag = false;

	@Override
	public int compareTo(Node other) {
		if (this.avgArea < other.avgArea)
			return 1;
		else if (this.avgArea > other.avgArea)
			return -1;
		else // 如果 avgArea 相等,比较 minNum
			return Integer.compare(this.minNum, other.minNum);
	}

}

发现超时了。
image.png
这里我们可以从 io 上进行优化,这里 BufferedReader 读入数据还不够快,我们改为使用 StreamTokenizer。当数据比较大的时候读取很慢!所以需要使用快读。我们快读主要是使用 java.io 包的 StreamTokenizer 类。

优化后:

java 复制代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

// L2-007 家庭房产
public class L2_7 {
	private static int[] parent = new int[10001]; // 记录对应编号的根节点
	private static boolean[] vis = new boolean[10001]; // 用来标记输入时所有出现的编号

	public static void main(String[] args) throws IOException {
		StreamTokenizer tokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

		// 按照编号存储
		Node[] node = new Node[10001];
		// 并查集:初始化
		for (int i = 0; i < 10001; i++) {
			parent[i] = i;
			node[i] = new Node();
		}
		tokenizer.nextToken();
		int n = (int)tokenizer.nval;
		Data[] data = new Data[n];

		for (int i = 0; i < n; i++) {
			// 编号 父 母 k 孩子1 ... 孩子k 房产套数 总面积
			data[i] = new Data();
			tokenizer.nextToken();
			data[i].id = (int) tokenizer.nval;
			tokenizer.nextToken();
			data[i].fid = (int) tokenizer.nval;
			tokenizer.nextToken();
			data[i].mid = (int) tokenizer.nval;
			tokenizer.nextToken();
			data[i].k = (int) tokenizer.nval;

			// 标记已经处理过的编号
			vis[data[i].id] = true;

			// 把父母融入到一个大集合中
			if (data[i].fid != -1) {
				vis[data[i].fid] = true; // 标记已经处理过的编号
				union(data[i].id, data[i].fid);
			}
			if (data[i].mid != -1) {
				vis[data[i].mid] = true; // 标记已经处理过的编号
				union(data[i].id, data[i].mid);
			}
			// 处理孩子
			for (int j = 0; j < data[i].k; j++) {
				tokenizer.nextToken();
				data[i].cid[j] = (int) tokenizer.nval;
				vis[data[i].cid[j]] = true; // 标记已经处理过的编号
				union(data[i].id, data[i].cid[j]);
			}

			tokenizer.nextToken();
			data[i].house = (int) tokenizer.nval;
			tokenizer.nextToken();
			data[i].area = (int) tokenizer.nval;
		}

		// 先记录最小编号,累加房产套数 面积
		for (int i = 0; i < n; i++) {
			int root = find(data[i].id); // 找到当前编号的根节点
			node[root].flag = true; // 在树的根节点标记是一个大家庭
			node[root].avgHouse += data[i].house; // 人均房产套数
			node[root].minNum = root; // 家庭成员的最小编号
			node[root].avgArea += data[i].area; // 人均房产面积
		}

		// 累加家庭成员
		int family_count = 0;
		for (int i = 0; i < 10001; i++) {
			if (vis[i]) {
				int root = find(i);
				node[root].count++; // 计算每个大家庭总人数
			}
			if (node[i].flag) {
				family_count++; // 计算有几个大家庭
			}
		}

		// 算人均房产套数 人均房产面积
		for (int i = 0; i < 10001; i++) {
			if (node[i].flag) {
				node[i].avgHouse = node[i].avgHouse * 1.0 / node[i].count;
				node[i].avgArea = node[i].avgArea * 1.0 / node[i].count;
			}
		}

		// 排序
		Arrays.sort(node);

		System.out.println(family_count);
		for (int i = 0; i < family_count; i++) {
			// 家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积
			System.out.printf("%04d %d %.3f %.3f\n", node[i].minNum, node[i].count, node[i].avgHouse, node[i].avgArea);
		}
	}

	// 合并
	private static void union(int id, int cid) {
		// 找到这两个编号所在树中的根节点
		int ra = find(id);
		int rb = find(cid);

		// 让最小的编号作为根节点
		if (ra > rb) {
			parent[ra] = rb;
		} else {
			parent[rb] = ra;
		}
	}

	// 查找
	private static int find(int id) {
		int root = id;
		// 循环找到当前数的根节点,即根节点的 parent 指向自己
		// 这样做的目的是找到元素 id 所在的集合的根节点
		while (parent[root] != root) {
			// 获取当前结点的根编号
			root = parent[root];
		}
		// 压缩路径,减少树的层数,防止树的退化。
		// 将 x 到根节点的路径上的所有节点直接连接到根节点上,从而减少树的深度
		while (parent[id] != root) {
			int temp = parent[id]; // 拿到当前节点的根节点编号
			parent[id] = root; // 连接到新的根节点
			id = temp; // 继续处理下一个节点
		}
		return root;
	}

}

class Data {
	int id; // 当前编号
	int fid, mid; // 父母编号
	int k, house, area;
	int[] cid = new int[10]; // 家庭
}

class Node implements Comparable<Node> {
	int minNum; // 家庭最小编号
	int count; // 家庭人口数
	double avgHouse; // 人均房产套数
	double avgArea; // 人均房产面积
	boolean flag = false;

	@Override
	public int compareTo(Node other) {
		if (this.avgArea < other.avgArea)
			return 1;
		else if (this.avgArea > other.avgArea)
			return -1;
		else // 如果 avgArea 相等,比较 minNum
			return Integer.compare(this.minNum, other.minNum);
	}

}
image.png
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句