天梯题集——家庭房产（并查集）

迈不过友情╰ 2022-12-23 07:10 136阅读 0赞

### 家庭房产 ###

![t1][]  
![t2][]

--------------------

#### 解题步骤 ####

**①、并查集**  
将每个家庭都看成一个集合，再统计每个家庭的人数、房产套数、总面积。  
**②、计算有效数据**  
对于每个家庭来说  
人均房产套数：房产套数/家庭人数  
人均房产面积：总面积/家庭人数  
**③、排名**  
利用 sort() 函数得出排名。

--------------------

实现代码

#include<bits/stdc++.h>
    using namespace std;
    int u[10010], C[10010], S[10010];
    bool judge[10010]={ false};
    struct node{ 
    	int sum_c;
    	int sum_s;
    	int min_bh;
    	int men;
    	double pj_s;
    	double pj_c;
    }f[10010];
    
    int get_(int x){ 
    	if(u[x]==x) return x;
    	return u[x]=get_(u[x]);
    }
    
    bool cmp1(node a, node b){ 
    	return a.sum_c>b.sum_c;
    }
    
    bool cmp2(node a, node b){ 
    	if(a.pj_s==b.pj_s)
    		return a.min_bh<b.min_bh;
    	return a.pj_s>b.pj_s;
    }
    
    int main(){ 
    	int n;
    	memset(C, 0, sizeof(C));
    	memset(S, 0, sizeof(S));
    	
    	for(int i=0; i<=10000; i++){ 
    		u[i] = i;
    		f[i].min_bh = 10010;
    		f[i].men = 0;
    	}
    		
    	scanf("%d", &n);
    	while(n--){ 
    		int num, fa, mu;
    		scanf("%d%d%d", &num, &fa, &mu);
    		judge[num]=true;
    		if(fa!=-1){ 
    			judge[fa]=true;
    			int x = get_(num);
    			u[x] = get_(fa);
    		}
    		if(mu!=-1){ 
    			judge[mu]=true;
    			int x = get_(num);
    			u[x] = get_(mu);
    		}
    		int k;
    		scanf("%d", &k);
    		for(int i=0; i<k; i++){ 
    			int child;
    			scanf("%d", &child);
    			judge[child]=true;
    			int x = get_(child);
    			u[x] = get_(num);
    		}
    		scanf("%d%d", &C[num], &S[num]);
    	}
    	
    	int c=0;
    	for(int i=0; i<=10000; i++){ 
    		if(judge[i]){ 
    			if(u[i]==i) c++;
    			else u[i] = get_(i);
    			f[u[i]].sum_c += C[i];
    			f[u[i]].sum_s += S[i];
    			f[u[i]].min_bh = min(i, f[u[i]].min_bh);
    			f[u[i]].men++;
    		}
    	}
    	//将有效的数据置前
    	sort(f, f+10010, cmp1);
    	for(int i=0; i<c; i++){ 
    		f[i].pj_c = (double)f[i].sum_c/f[i].men;
    		f[i].pj_s = (double)f[i].sum_s/f[i].men;
    	}
    	sort(f, f+c, cmp2);
    	printf("%d\n", c);
    	for(int i=0; i<c; i++){ 
    		printf("%04d %d %.3lf %.3lf\n", f[i].min_bh, f[i].men,
    		f[i].pj_c, f[i].pj_s);
    	}
    	
    	return 0;
    }

[t1]: /images/20221120/439cb351f1484cafb3a69da57b7703b5.png
[t2]: /images/20221120/e6da034e48334cdc9b7576be28c807dd.png