[PAT解题报告] Set Similarity
简单题，集合求交。正规做法是用数组存好，排好顺序，用O(n)的归并方法求交。
我直接用了C++
STL的set存了所有的集合，求交就不用排序了，用iterator迭代就可以了。求交的方法就是哪个iterator对应的数小，就移动哪个，如果相等就找到了一个相交的元素。当然还要算一下并集元素的个数，因为要算相似度，用交集元素个数除以并集元素个数。
#include <set>
#include <cstdio>
using namespace std;
set<int> a[52];
double give(int x,int y) {
int inter = 0, total = 0;
for (set<int>::iterator t1 = a[x].begin(), t2 = a[y].begin(); (t1 != a[x].end()) || (t2 != a[y].end()); ++total) {
if (t1 == a[x].end()) {
++t2;
}
else if (t2 == a[y].end()) {
++t1;
}
else if (*t1 == *t2) {
++inter;
++t1;
++t2;
}
else if (*t1 < *t2) {
++t1;
}
else {
++t2;
}
}
return inter * 100.0 / total;
}
int main() {
int n;
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
int x;
for (scanf("%d",&x);x;--x) {
int y;
scanf("%d",&y);
a[i].insert(y);
}
}
int m;
for (scanf("%d",&m);m;--m) {
int x,y;
scanf("%d%d",&x,&y);
printf("%.1lf%%\n", give(x - 1,y - 1));
}
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1063
查看1道真题和解析