Skip to content

Latest commit

 

History

History
85 lines (74 loc) · 4 KB

1114. Family Property.md

File metadata and controls

85 lines (74 loc) · 4 KB

【PAT A-1114】Family Property

题意概述

给定每个人的家庭成员以及他/她自己名字下的房产信息，我们需要知道每个家庭的规模，以及他们房产的平均面积和套数。

输入输出格式

输入第一行给出一个正整数 N。接下来 N 行，每行以$ID\ Father\ Mother\ k\ Child_1\cdots\ Child_k\ M_{estate}\ Area$格式提供拥有财产的人的信息。其中，ID 是每个人的唯一 4 位标识号；父亲和母亲是此人父母的 ID（如果父母去世，则对应值为-1）k 是此人的孩子数；$Child_i$是他/她孩子的 ID；$M_{estate}$是他/她名字下的房产总数；Area 是他/她的房产总面积。

首先在一行中打印家庭数量（将直接或间接相关的所有人都视为同一家庭）。然后以$ID\ M\ AVG_{sets}\ AVG_{area}$格式输出家庭信息。其中 ID 是家庭成员中最小的 ID；M 是家庭成员总数；$AVG_{sets}$是其房地产的平均套数；$AVG_{area}$是平均面积。平均值必须精确到小数点后 3 位。按平均面积降序的顺序输出家庭的相关信息，如果平均面积相同，则按 ID 的升序输出所有家庭的相关信息。

数据规模

$$0<N\le 1000,0\le k\le5$$

算法设计

使用并查集，由于成员 ID 是 4 位数字，并查集数组需开到${10}^4$。额外开辟两个数组 sets、area，分别存储一个家庭名下的房产总数和总面积。在读取输入数据时，用一个 unordered_set<gg> us 存储所有输入的人员编号。合并一行输入中的所有出现的 ID，并将成员的房产信息读取到 sets 和 area 中。注意，由于要求输出家庭中最小的 ID，可以在合并集合的时候，将根结点编号大的集合合并到跟结点编号小的集合，这样可以保证根结点的编号就是这个家庭中的最小编号。 定义一个 vector 类型变量 roots 存储所有家庭的根结点。遍历 us，将所有根结点编号记录到 roots 中，并将所有成员的房产信息累加到根结点的房产信息中。将 roots 按要求排序并输出。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
const gg MAX = 1e4 + 5;
vector<gg> ufs(MAX), num(MAX, 1), sets(MAX), area(MAX);
void init() { iota(ufs.begin(), ufs.end(), 0); }
gg findRoot(gg x) { return ufs[x] == x ? x : ufs[x] = findRoot(ufs[x]); }
void unionSets(gg a, gg b) {
    gg ra = findRoot(a), rb = findRoot(b);
    ufs[max(ra, rb)] = min(ra, rb);  //合并到根结点编号小的集合
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    gg ni;
    cin >> ni;
    unordered_set<gg> us;  //存储所有输入的人员编号
    while (ni--) {
        gg id, fi, mi, ki, ai;
        cin >> id >> fi >> mi >> ki;
        us.insert(id);
        if (fi != -1) {
            us.insert(fi);
            unionSets(id, fi);
        }
        if (mi != -1) {
            us.insert(mi);
            unionSets(id, mi);
        }
        while (ki--) {
            cin >> ai;
            us.insert(ai);
            unionSets(id, ai);
        }
        cin >> sets[id] >> area[id];  //房产总数存储在sets中，面积存储在area中
    }
    vector<gg> roots;  //存储所有集合的根结点
    for (auto& i : us) {
        gg r = findRoot(i);  //根结点
        if (find(roots.begin(), roots.end(), r) == roots.end()) {
            roots.push_back(r);
        }
        if (i != r) {  //如果i不是跟结点，将i的相关信息累加到跟结点r中
            num[r]++;
            sets[r] += sets[i];
            area[r] += area[i];
        }
    }
    sort(roots.begin(), roots.end(), [](int a, int b) {
        return make_pair(area[b] * 1.0 / num[b], a) <
               make_pair(area[a] * 1.0 / num[a], b);
    });  //排序
    cout << fixed << setprecision(3) << setfill('0') << roots.size() << "\n";
    for (gg i : roots) {
        cout << setw(4) << i << " " << num[i] << " " << sets[i] * 1.0 / num[i]
             << " " << area[i] * 1.0 / num[i] << "\n";
    }
    return 0;
}