L2-005. 集合相似度
给定两个整数集合,它们的相似度定义为:Nc/Nt*100%。其中Nc是两个集合都有的不相等整数的个数,Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。
输入格式:
输入第一行给出一个正整数N(<=50),是集合的个数。随后N行,每行对应一个集合。每个集合首先给出一个正整数M(<=104),是集合中元素的个数;然后跟M个[0, 109]区间内的整数。
之后一行给出一个正整数K(<=2000),随后K行,每行对应一对需要计算相似度的集合的编号(集合从1到N编号)。数字间以空格分隔。
输出格式:
对每一对需要计算的集合,在一行中输出它们的相似度,为保留小数点后2位的百分比数字。
输入样例:33 99 87 1014 87 101 5 877 99 101 18 5 135 18 9921 21 3输出样例:
50.00%33.33%
分析:我怎么感觉这题目题意不明啊。。。然后我去看了下别人的题意分析,懂了,简单说嘛就是nc代表了两个集合中相等的元素的个数,nz代表了两个集合的元素总个数,
nz其实就是两个集合的总元素减去两个集合中的相等的元素,即 s[i].size()+s[j].size()-nc,这里用到了STL中的set容器,其中迭代器iterator可以用来扫一遍集合中的元素
方便比较。
一开始我在想怎么区分该集合是第几个集合? 然后想了一下,既然set<int>s表示的是s是一个集合,那么set<int>s[maxn]表示的就是有maxn个集合,其中数组的下标可以用来表示这是第几个集合。
1 #include2 using namespace std; 3 const int maxn=1e4+5; 4 set s[52]; 5 int a[maxn]; 6 set ::iterator it; 7 8 int main(){ 9 int n;10 cin>>n;11 int m, len=0;12 for(int i=0; i >m;15 int x;16 for(int j=0; j >x;18 s[len].insert(x);19 }20 }21 int sum, a, b;22 cin>>sum;23 for(int i=0; i >a>>b;25 double same=0, total=0;26 for(it=s[b].begin(); it!=s[b].end(); it++){27 if(s[a].count(*it)) same++;28 }29 total=s[a].size()+s[b].size()-same;30 printf("%.2f%\n", same/total*100);31 }32 33 34 return 0;35 }