首页 > 代码库 > PAT甲题题解-1063. Set Similarity (25)-set的使用
PAT甲题题解-1063. Set Similarity (25)-set的使用
题意:
两个整数集合,它们的相似度定义为:nc/nt*100%
nc为两个集合都有的整数
nt为两个集合一共有的整数
注意这里的整数都是各不相同的,即重复的不考虑在内。
给出n个整数集合,和k个询问,让你输出每个询问中两个集合的相似度。
因为数值范围在[0,10^9],开不了这么大的数组来标记某个数的出现,所以一开始用了map
然而最后一个样例超时了
因为题目说了不包含重复的元素,所以想到用set来存储
set的大小即为集合不相同的整数个数
那么寻找a和b集合相同的元素个数,只需要遍历一下a集合的元素,看是否能在b集合中找到即可
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <map> #include <set> using namespace std; const int maxn=10000*50+1; set<int> sets[51]; int n; int m[51]; int dif[51];//dif[i]为第i个集合不同的元素个数 double ans[51][51]; /** 把所有集合对的相似度先求出来,之后询问的时候直接访问即可 */ void solve(int n){ int val; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ int same=0; set<int>::iterator it,findit; for(it=sets[i].begin();it!=sets[i].end();it++){ val=*it; findit=sets[j].find(val); if(findit!=sets[j].end()) same++; } ans[i][j]=ans[j][i]=same*1.0/(dif[i]+dif[j]-same); } } } int main() { scanf("%d",&n); int val; memset(dif,0,sizeof(dif)); for(int i=1;i<=n;i++){ scanf("%d",&m[i]); for(int j=0;j<m[i];j++){ scanf("%d",&val); sets[i].insert(val); } dif[i]=sets[i].size(); } solve(n); int k; int a,b; scanf("%d",&k); for(int i=0;i<k;i++){ scanf("%d %d",&a,&b); printf("%.1lf%%\n",ans[a][b]*100); } return 0; }
PAT甲题题解-1063. Set Similarity (25)-set的使用
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。