小明爱集合-开发者社区

题目描述

最近小明又喜欢上了集合，于是他提出了很多有关集合的问题，其中的一个问题是给你两个集合（集合内部没有重复的元素），让你求集合的相似度是多少，集合的相似度定义如下：

2个集合的相似度 = 相同元素的个数/(相同元素个数+不同元素个数)

聪明的你可以帮助小明解决这个问题吗？

输入格式

题目含有多组数据，第一行一个数T，表示数据的组数；

对于每组数据：

第一行包括两个数n,m，分别表示两个集合元素的个数(1<=n,m<100000)；

第二行n个数表示前一集合的n个数，以空格隔开；

第三行m个数表示后一集合的m个数，以空格隔开；

其中对于两集合中任意数ai，有。

输出格式

对于每组数据，输出两个集合的相似度，输出结果乘100 后取整数部分。

样例

【样例输入】

2 3

1 2

2 3 4

3 3

5 3 4

3 4 1

【样例输出】

数据范围与提示

对于10%的数据，1 <= T <= 2， n,m<= 4

对于50%的数据，1 <= T<= 4，n,m<= 1024

对于100%的数据，1 <= T<=10， n,m<= 100000

一些想法

这道题用 set 做非常简单，因为 set 是可以自动去重的，那输入两个数组的数时可以直接放入 set 中，它会自动去重，也就是将两个数组相同的数直接去掉。然后 sum 等于两个数组的数个数总和减去 set 中数的个数（去重去了几个数，也就是两个集合中重复元素的数量）。然后最终答案等于（要 double 类型的，因为答案是小数点乘100，要先等于小数）double 类型的 sum 除以 set 的长度，这里可以理解为重复元素数量在并集元素数量中的占比，最后输出 int 类型的答案乘 100 ，换行。最后要清空 set ，否则有多组数据时，后面的会答案错误。

注：

输出答案转换类型时要 (int)(ss*100)，不能(int) ss*100，否则会先转换 ss 的类型，从而导致精确度丢失。~~别问我是怎么知道的~~

用一个别的数先储存 set 的长度减少写代码时的麻烦也是可以的！

AC代码

#include<bits/stdc++.h> using namespace std; int t; set<int> s; int main(){ cin>>t; while(t--){ int n,m,sum=0; cin>>n>>m; for(int i=1;i<=n;i++){ int x; cin>>x; s.insert(x); } for(int i=1;i<=m;i++){ int x; cin>>x; s.insert(x); } sum=n+m-s.size(); double ss=(double)sum/s.size(); cout<<(int)(ss*100)<<endl; s.clear(); } return 0; }