首页 > 代码库 > 天梯杯 L2-005. 集合相似度
天梯杯 L2-005. 集合相似度
L2-005. 集合相似度
时间限制
400 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
陈越
给定两个整数集合,它们的相似度定义为:Nc/Nt*100%。其中Nc是两个集合都有的不相等整数的个数,Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。
输入格式:
输入第一行给出一个正整数N(<=50),是集合的个数。随后N行,每行对应一个集合。每个集合首先给出一个正整数M(<=104),是集合中元素的个数;然后跟M个[0, 109]区间内的整数。
之后一行给出一个正整数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存下来 这道题目让我熟悉了set的用法 以前知道这东西,但一直没怎么用,今天敲了一遍,感觉收获蛮大的
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<set> using namespace std; int main() { int n; scanf("%d",&n); set<int>s[55]; for(int i=1;i<=n;i++) { int m; scanf("%d",&m); for(int j=0;j<m;j++) { int a; scanf("%d",&a); s[i].insert(a); } } int k; scanf("%d",&k); while(k--) { int c,d; scanf("%d%d",&c,&d); int num = 0; set<int>::iterator it; for(it=s[c].begin();it!=s[c].end();it++) { if(s[d].find(*it)!=s[d].end()) num++;//找相同个数 } int nt = s[c].size()+s[d].size()-num;//两个集合合在一起去掉重复个数之后剩下个数
printf("%.2lf%%\n",num*1.0/nt*100);
}
return 0;
}
天梯杯 L2-005. 集合相似度
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。