PTA 7-9 集合相似度（STL之set初体验）

7-9 集合相似度（25 分）

给定两个整数集合，它们的相似度定义为： $N^{ c } / N^{ t } \times 100 %$ 。其中 $N^{ c }$ 是两个集合都有的不相等整数的个数， $N^{ t }$ 是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入格式：

输入第一行给出一个正整数 $N$ （ $\leq 50$ ），是集合的个数。随后 $N$ 行，每行对应一个集合。每个集合首先给出一个正整数 $M$ （ $\leq 1 0^{ 4 }$ ），是集合中元素的个数；然后跟 $M$ 个 $[0, 1 0^{ 9 }]$ 区间内的整数。

之后一行给出一个正整数 $K$ （ $\leq 2000$ ），随后 $K$ 行，每行对应一对需要计算相似度的集合的编号（集合从1到 $N$ 编号）。数字间以空格分隔。

输出格式：

对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。

输入样例：

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

输出样例：

50.00%
33.33%

思路：这题样例就能看到，同一个集合里面可能就有重复的元素（你这题就是否定了高中学的集合的元素的唯一性），虽然没用过set，但是set中不会出现重复样例，并且可以用logn的find来查找元素，所以这题用set极好

主要学习代码中有关set的部分，尤其是遍历那里

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<set>
typedef long long ll;
using namespace std;
const int maxn = 10000 + 10;
set<int> a[10000 + 10];

void solve(int x, int y){
	int s1 = a[x].size();
	int s2 = a[y].size();
	int nc = 0;
	set<int>::iterator it= a[x].begin();
	for(it = a[x].begin(); it !=a[x].end(); it++){//这里不要习惯性的写int了！ 
		if(a[y].find(*it)!=a[y].end())nc++;
	}
	int nt = s1 + s2 - nc;
	printf("%.2lf%%",(double)100.0*nc/nt);
}
int main(){
    int n , m;
    int x, y;
    int nn;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
    	scanf("%d", &nn);
		while(nn--){
			int aa;
			scanf("%d", &aa);
			a[i].insert(aa);
		} 
	}
	scanf("%d", &m);
	while(m--){
		scanf("%d %d", &x, &y);
		solve(x, y);
	}
	
    return 0;
}

另补充一点：

unique可以删除有序数组中的重复元素

秒客网