PAT甲级1114Family Property

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805356599820288

题解

题目要求

• 给出每个人的家庭成员和属于他的房产信息，请计算每个家庭的成员数、房产平均面积、房产数
• 输入
  • N：不超过1000，人的数量
  • N个有房产的人的信息：id、父亲、母亲、孩子、房产数、房产面积
• 输出
  • 输出家庭数量
  • 输出每个家庭的最小id、人数、平均房产数、平均房产面积（按平均房产面积降序，然后按最小id升序）

解题思路

• 题目只给了N个有房产的人的信息，但人并不一定是N个，也不一定是10000个，因此需要标记一个id是否有效（即这个人是否存在）

  如果一个人的代表人是-1，则这个人不存在

• 题目要求输出每个家庭的最小id，这个最小id可以在建立家族关系时保存，即合并两个家族时取较小的id

代码

// Problem: PAT Advanced 1114
// URL: https://pintia.cn/problem-sets/994805342720868352/problems/994805356599820288
// Tags: 并查集 路径压缩

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

struct Family{
    int id, memberNum = 0;
    double estateNum = 0, estateArea = 0;
};

const int MAXN = 10000;
int representative[MAXN];
int estateArea[MAXN];
int estateNum[MAXN];
Family families[MAXN];

int findRepresentative(int x){
    return (x == -1 || x == representative[x]) ? x : representative[x] = findRepresentative(representative[x]);
}

void UNION(int a, int b){
    int ra = findRepresentative(a), rb = findRepresentative(b);
    // 取家族中的最小id作为representative
    if (rb < ra)
        representative[ra] = rb;
    else if (ra < rb)
        representative[rb] = ra;
}

bool familyCmp(Family& f1, Family& f2){
    return f1.estateArea == f2.estateArea ? f1.id < f2.id : f1.estateArea > f2.estateArea;
}

int main()
{
    // 初始化家族关系
    for (int i = 0; i < MAXN; i++){
        representative[i] = -1; // representative为-1代表该人不存在
        families[i].id = i; // 该人作为代表者时，对应一个家族。该id是为了排序用
    }
    // 建立家族关系
    int n, id, fatherID, motherID, k, childID, num, area;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d%d%d%d", &id, &fatherID, &motherID, &k);
        if (representative[id] == -1)
            representative[id] = id; // 记录：该人存在
        if (fatherID != -1){
            if (representative[fatherID] == -1)
                representative[fatherID] = fatherID; // 记录：该人存在
            UNION(id, fatherID);
        }
        if (motherID != -1){
            if (representative[motherID] == -1)
                representative[motherID] = motherID; // 记录：该人存在
            UNION(id, motherID);
        }
        for (int j = 0; j < k; j++){
            scanf("%d", &childID);
            if (representative[childID] == -1)
                representative[childID] = childID; // 记录：该人存在
            UNION(id, childID);
        }
        scanf("%d%d", &estateNum[id], &estateArea[id]);
    }

    // 统计家族数据
    int tmp;
    for (int i = 0; i < MAXN; i++){
        tmp = findRepresentative(i);
        if (tmp != -1){ // 如果这个人存在
            families[tmp].memberNum += 1;
            families[tmp].estateNum += estateNum[i];
            families[tmp].estateArea += estateArea[i];
        }
    }


    vector<Family> v;
    for(int i = 0; i < MAXN; i++){
        if (families[i].memberNum > 0){
            families[i].estateArea = families[i].estateArea / families[i].memberNum;
            families[i].estateNum = families[i].estateNum / families[i].memberNum;
            v.push_back(families[i]);
        }

    }
    printf("%d
", v.size());
    sort(v.begin(), v.end(), familyCmp);
    for (int i = 0; i < v.size(); i++){
        printf("%04d %d %.3f %.3f
", v[i].id, v[i].memberNum, v[i].estateNum, v[i].estateArea);
    }

    return 0;
}

---

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!

---