PAT A1063 Set Similarity (25分)

前言

正文

参考题解
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
/* 题意：对于给定的任意个集合，进行k次查询，每次查询要求出对于给定的两个集合之间的相似度； 集合的相似度定义为两个集合的交集的元素数量/两个集合的并集的元素数量。结果保留一位小数。 注意点： 可以利用并集的元素个数等于两个集合元素之和减去交集的元素个数 */
map<int,set<int>> mp;
//获取交集的元素个数 
int getNc(set<int> &a,set<int> &b){
	int cnt=0;
	for(auto x=a.begin();x!=a.end();x++){
		if(b.find(*x)!=b.end())cnt++;
	}
	return cnt;
}
int main(){
	int n,m,mi,Nc,Nt;
	double per;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&m);
		while(m--){
			scanf("%d",&mi);
			mp[i].insert(mi);
		}
	}
	int k,a,b;
	scanf("%d",&k);
	for(int i=0;i<k;i++){
		scanf("%d%d",&a,&b);
		Nc=getNc(mp[a],mp[b]);
		Nt=mp[a].size()+mp[b].size()-Nc;//并集的元素个数 
		per=(double)Nc/Nt;
		printf("%.1f\%\n",per*100);
	} 
	return 0;
}