【PAT】A1063 Set Similarity

Given two sets of integers, the similarity of the sets is defined to be N​c​​/N​t​​×100%, where N​c​​ is the number of distinct common numbers shared by the two sets, and N​t​​ is the total number of distinct numbers in the two sets. Your job is to calculate the similarity of any given pair of sets.

Input Specification:

Each input file contains one test case. Each case first gives a positive integer N (≤50) which is the total number of sets. Then Nlines follow, each gives a set with a positive M (≤10​4​​) and followed by M integers in the range [0,10​9​​]. After the input of sets, a positive integer K (≤2000) is given, followed by K lines of queries. Each query gives a pair of set numbers (the sets are numbered from 1 to N). All the numbers in a line are separated by a space.

Output Specification:

For each query, print in one line the similarity of the sets, in the percentage form accurate up to 1 decimal place.

Sample Input:

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

Sample Output:

50.0% 33.3%

解题思路：

题目大意：给出n个序列和其中的数，要求给出指定两个集合的(相同个数)/(不同个数)的比率

使用STL中的set容器，因为set容器自动去掉重复的数并且按升序排序集合里的数。代码分为2段：首先按照要求输入数据，即输入“要输入的集合数n”和“n个集合，每个集合要输入的数m，以及输入m个数”，用set的insert()函数可以过滤掉重复的数据；下一步是整理数据，例如统一确定st[set2]是被查找的集合，循环st[set1]，如果找到st[set2].find(*it)!=st[set2].end()，意思是非空，也就是找到了，就相同数加一，反之就是st[set1]中有的数在st[set2]中是没有的，那么把st[set2].size()++，每一次输出即可。

总结：在st[set2].find(*it)!=st[set2].end()，这里需要思路清晰，大脑不能犯糊涂，对照1查2,2中查不到就++，不是对照1查1

代码： 

#include <stdio.h> #include <set> using namespace std; set<int> st[55];int main(){int n,m,x,set1,set2,inquiry,same,count=0;scanf("%d",&n); //集合的数量n//输入数据 for(int i=1;i<=n;i++){scanf("%d",&m); //集合中的数量mfor(int j=0;j<m;j++){scanf("%d",&x); //集合中的每一个数，赋值为xst[i].insert(x); //将数插入到第i个集合中 } }//整理数据scanf("%d",&inquiry); //需要查询的次数for(int i=0;i<inquiry;i++){same=0;scanf("%d%d",&set1,&set2); //比较的集合编号int count=st[set2].size();for(set<int>::iterator it=st[set1].begin();it!=st[set1].end();it++){//从第一个集合中的每一个数，看是否有数和st[set2]中的数一致，一致就same++,不一致则count++if(st[set2].find(*it)!=st[set2].end()){//一开始弄错的地方same++;//printf("%d\n",same);}else{count++;//printf("c%d\n",count);}}printf("%.1lf%%\n",(double)(same*100.0/count));}return 0; }

 

总结

以上是生活随笔为你收集整理的【PAT】A1063 Set Similarity的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。