团体程序设计天梯赛-练习集 L2-005 集合相似度 (25分) SET做法超级简便！

忘是亡心i 2023-10-11 14:52 5阅读 0赞

### L2-005 集合相似度 (25分) ###

给定两个整数集合，它们的相似度定义为：Nc/Nt×100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

**输入格式：**  
输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤10^4），是集合中元素的个数；然后跟M个\[0,10的9次方\]区间内的整数。之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。

**输出格式：**  
对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。

**输入样例：**

3
    3 99 87 101
    4 87 101 5 87
    7 99 101 18 5 135 18 99
    2
    1 2
    1 3

**输出样例：**

50.00%
    33.33%

> 本题思路：利用set集合的特殊性质：不会存重复的元素，即可解答本题。

#include<bits/stdc++.h>
    const int N = 1005;
    using namespace std;
    set<int> se[55];
    set<int>::iterator ite;
    
    int n, m, k, ans;
    
    int main(){
        
    	cin >> n;
    	for(int i = 1 ; i <= n; i ++){
        
    		cin >> m;
    		while(m--){
        
    			cin >> ans;
    			se[i].insert(ans);
    		}
    	}
    
    	int f1, f2;
    	cin >> k;
    	while(k--){
        
    		cin >> f1 >> f2;
    		int co = 0, sumCo = se[f1].size()+se[f2].size();
    		for(ite = se[f1].begin(); ite != se[f1].end(); ite++){
        
    			if(se[f2].find(*ite) != se[f2].end()){
        //计算两个集合都有的不相等整数的个数
    				co++;
    				sumCo--;
    			}
    		}
    		printf("%.2lf%\n", co*100.0/sumCo);
    	}
    
    	return 0;
    }