PAT甲级1114Family Property

Posted on | | Visitors:
Words count in article: 802 字 | Reading time ≈ 4 分

题目链接

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

题解

题目要求

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

解题思路

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

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

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
// 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\n", v.size());
    sort(v.begin(), v.end(), familyCmp);
    for (int i = 0; i < v.size(); i++){
        printf("%04d %d %.3f %.3f\n", v[i].id, v[i].memberNum, v[i].estateNum, v[i].estateArea);
    }

    return 0;
}

作者：@臭咸鱼

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

欢迎讨论和交流!