如何查网站备案信息,企业信用信息公示年报,烤肉自助餐网站建设,桂林象鼻山景区介绍题目 题目大意
共有n个户主#xff0c;每个户主的房产按照“ 户主id 父亲id 母亲id 孩子个数 孩子的id 房产数 房产面积 ”的格式给出。如果父亲或母亲不存在#xff0c;值为-1。每个户主及其父亲母亲孩子可以构成一个家庭#xff0c;不同户主如果有相同的家人#xff0c;…题目 题目大意
共有n个户主每个户主的房产按照“ 户主id 父亲id 母亲id 孩子个数 孩子的id 房产数 房产面积 ”的格式给出。如果父亲或母亲不存在值为-1。每个户主及其父亲母亲孩子可以构成一个家庭不同户主如果有相同的家人那么就可以将两家联系起来组成一个大家庭。要求输出家庭数和家庭id取家庭中的最小id平均房产数平均房产面积。输出按照平均房产面积从大到小排序如果相同按id从小到大排序。
思路
从一堆人中组团并求团的个数并查集。由题可知户主母亲父亲孩子不管是谁的id都是等价的它们的共同祖先家庭id就是这群人中的最小id题目中规定的。每个家庭中的人可以合并不同家庭中的人也可合并合并的条件就是看两个人的家庭id是否相同以及一个人是否存在于两个家庭中。pre[]数组即记录每个人对应的家庭idfind()数组找到根节点即其所属最大家庭的idcombine()合并两个人或集合init()初始化完成并查集的建立。另外还需要记录每个人对应的家庭成员数、房产数、房产大小只有根节点对应的值才有效。
代码
#include iostream
#include vector
#include algorithm
using namespace std;int n;
int pre[10000]; // 并查集记录前驱节点为家庭id的最小值
vectorint num(10000, 1); // 家庭成员数初始化为1
int amount[10000] {0}; // 房产数
int area[10000] {0}; // 房产大小int find(int a){if (pre[a] a){return a;}else{return pre[a] find(pre[a]);}
} // 找某元素的根节点void combine(int a, int b){int root_a find(a);int root_b find(b);if (root_a root_b){return;}if (root_a root_b){pre[root_b] root_a;num[root_a] num[root_b];amount[root_a] amount[root_b];area[root_a] area[root_b];}else{pre[root_a] root_b;num[root_b] num[root_a];amount[root_b] amount[root_a];area[root_b] area[root_a];}
} // 合并两个不同的集合void init(){cin n;for (int i 0; i 10000; i){pre[i] i;} // 初始化pre数组for (int i 0; i n; i){int id, f, m, k, amounts, areas;vectorint p;cin id f m k;p.push_back(id);if (f ! -1) p.push_back(f);if (m ! -1) p.push_back(m);for (int j 0; j k; j){int child;cin child;p.push_back(child);}cin amounts areas;sort(p.begin(), p.end());for (int j 0; j (int)p.size(); j){combine(p[j], p[0]);} // 合并每一个家庭成员int root find(id);amount[root] amounts;area[root] areas; // 累加到一个家庭中的根节点}
}struct family{int id;int total;double avg_amount;double avg_area;
};bool cmp(family x, family y){if (x.avg_area y.avg_area){return x.id y.id;}return x.avg_area y.avg_area;
}int main(){init();vectorfamily res;for (int i 0; i 10000; i){if (pre[i] i (amount[i] 0 || area[i] 0)){res.push_back({i, num[i], amount[i] * 1.0 / num[i], area[i] * 1.0 / num[i]});}}sort(res.begin(), res.end(), cmp);cout (int)res.size() endl;for (int i 0; i (int)res.size(); i){printf(%04d %d %.3lf %.3lf\n, res[i].id, res[i].total, res[i].avg_amount, res[i].avg_area);}return 0;
}
