[数据结构与算法]个人练习-PAT甲级-1114 Family Property

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805356599820288

题目大意：给出一系列人的数据，每个人的数据包含【自己的id，父母的id，有几个孩子，孩子们的id，有几套房，所有房子面积总和】

直接或间接联系起来的都算一家人，求家庭的个数，并输出【家庭成员中最小的编号，家庭成员个数，平均房套数，平均房面积数】输出顺序先按平均面积，再按最小编号。

思路：一开始想用并查集做（实际上家庭本身也是个并查集）但由于最后要输出【一个家庭中最小的编号】，那么肯定会要对并查集遍历。但如果仅仅用保存父亲对方法来建立并查集的话，只能从叶子结点向上搜，效率不高。而且一个人可能又有父亲又有母亲，指向谁起始也都不太合适。总之仅仅用数组麻烦很多，所以直接上STL的set。

给出一个set的vectorfml，每个fml[i]内装同一个家庭的成员编号。我们无需关注人和人之间的父母亲关系，对每一行的数据，只需将【本人】【父母】（如果健在）【孩子】全都放进暂时的一个vectorppl里，因为他们必然是属于一个set的。然后遍历ppl，如果找到了一个人所属的set的编号fm，那么整个ppl里的人肯定都属于fml[fm]了。但还没有结束，如果这个ppl里又找到一个人所属的set的编号fm2，并且它不等于fm，此时就需要合并两个setfml[fm]和fml[fm2]。

举例来说，就是第一行给出【你爸】【你哥】；第二行给出【你妈】【你姐】；第三行给出【你】【你爸】【你妈】。这时你突然发现，扫描到【你】这一行时，【你爸】所属的set是0，你妈所属的set是1，所以要将fml[0]和fml[1]合并后，再将第三行的【你】【你爸】【你妈】插入合并后的set。

        int fm = -1;
        for (int j = 0; j < ppl.size(); j++) {
            if (fm == -1) {
                if (findFml(ppl[j]) != -1)
                    fm = findFml(ppl[j]);
            }
            else {
                if (findFml(ppl[j]) != -1 &&findFml(ppl[j]) != fm) {
                    int fm2 = findFml(ppl[j]);
                    fml[fm].insert(fml[fm2].begin(), fml[fm2].end());
                    fml.erase(fml.begin()+fm2, fml.begin()+fm2+1);
                }
            }
        }

在第一次遍历了ppl后如果还没有找到属于他们的set，说明暂时他们还没有和任何家庭有联系，要新开一个set放他们。

        if (fm != -1) {
            for (int j = 0; j < ppl.size(); j++)
                fml[fm].insert(ppl[j]);
        }
        else {
            set<int> tmp;
            fml.push_back(tmp);
            for (int j = 0; j < ppl.size(); j++)
                fml.back().insert(ppl[j]);
        }

为了输出方便，我们定义一个类Node。

class Node{
public:
    int id, num;
    double avg_set, avg_area;
};

因为人数，房套数，面积等变量在set的合并时都容易丢失，所以都先存在以个人id为下标的数组里面。最后在遍历fml时再整合，计算平均值。

    for (int fm = 0; fm < fml.size(); fm++) {
        ret[fm].num = fml[fm].size();
        int min_id = 10000;
        for (set<int>::iterator it = fml[fm].begin(); it != fml[fm].end(); it++) {
            if (*it < min_id)
                min_id = *it;
            ret[fm].avg_area += 1.0 * space[*it];
            ret[fm].avg_set += 1.0 * num_house[*it];
        }
        ret[fm].id = min_id;
        ret[fm].avg_area /= ret[fm].num;
        ret[fm].avg_set /= ret[fm].num;
    }

排好序后输出即可。

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>


using namespace std;


class Node{
public:
    int id, num;
    double avg_set, avg_area;
};


int space[10000];
int num_house[10000];
vector<set<int>> fml;


int findFml(int id) {
    for (int i = 0; i < fml.size(); i++) {
        if (fml[i].count(id))
            return i;
    }
    return -1;
}


bool cmp(Node x, Node y) {
    if (abs(x.avg_area - y.avg_area) >= 0.001)
        return x.avg_area - y.avg_area > 0;
    else
        return x.id < y.id;
}


int main() {
    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        int id, fa, mo, k, m, area;
        vector<int> ppl;
        scanf("%d %d %d %d", &id, &fa, &mo, &k);

        ppl.push_back(id);
        if (fa != -1) ppl.push_back(fa);
        if (mo != -1) ppl.push_back(mo);

        for (int j = 0; j < k; j++) {
            int child;
            scanf("%d", &child);
            ppl.push_back(child);
        }

        int fm = -1;
        for (int j = 0; j < ppl.size(); j++) {
            if (fm == -1) {
                if (findFml(ppl[j]) != -1)
                    fm = findFml(ppl[j]);
            }
            else {
                if (findFml(ppl[j]) != -1 &&findFml(ppl[j]) != fm) {
                    int fm2 = findFml(ppl[j]);
                    fml[fm].insert(fml[fm2].begin(), fml[fm2].end());
                    fml.erase(fml.begin()+fm2, fml.begin()+fm2+1);
                }
            }
        }

        if (fm != -1) {
            for (int j = 0; j < ppl.size(); j++)
                fml[fm].insert(ppl[j]);
        }
        else {
            set<int> tmp;
            fml.push_back(tmp);
            for (int j = 0; j < ppl.size(); j++)
                fml.back().insert(ppl[j]);
        }

        scanf("%d %d", &m, &area);
        num_house[id] += m;
        space[id] += area;
    }

    printf("%d\n", fml.size());
    vector<Node> ret(fml.size());
    for (int fm = 0; fm < fml.size(); fm++) {
        ret[fm].num = fml[fm].size();
        int min_id = 10000;
        for (set<int>::iterator it = fml[fm].begin(); it != fml[fm].end(); it++) {
            if (*it < min_id)
                min_id = *it;
            ret[fm].avg_area += 1.0 * space[*it];
            ret[fm].avg_set += 1.0 * num_house[*it];
        }
        ret[fm].id = min_id;
        ret[fm].avg_area /= ret[fm].num;
        ret[fm].avg_set /= ret[fm].num;
    }

    sort(ret.begin(), ret.end(), cmp);

    for (int fm = 0; fm < ret.size(); fm++)
        printf("%04d %d %.3f %.3f\n", ret[fm].id, ret[fm].num, ret[fm].avg_set, ret[fm].avg_area);


    return 0;
}