L2-005 集合相似度

L2-005 集合相似度 （25 分)

给定两个整数集合，它们的相似度定义为：Nc/Nt×100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入格式：

输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤104），是集合中元素的个数；然后跟M个[0,109]区间内的整数。

之后一行给出一个正整数K（≤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%

思路 

题意很短，所以要看清。

两个集合都有的不相等整数的个数 等价于 两个集合的交集

两个集合一共有的不相等整数的个数等价于 两个集合的并集

注意：上边说的是集合，但是输入的数据有重复的。

所以用c++就用stl set集合就行了。

第一次写的时候，我是先放在数组中，然后再放到set中进行去重。因为这个数据量 不小，所以最后一组数据超时。

那我们输入的时候就直接放到set中，这样就节省了很多时间

代码

AC的代码

#include<cstdio>
#include<set>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 50 + 5;
set<int> s[maxn];
set<int>::iterator it;

double solve(int p, int q){
  int sum1 = 0;
  int sum2 = 0;
  for(it = s[p].begin(); it != s[p].end(); it++){
    int p = *it;;
    if(s[q].find(p) != s[q].end()){
      sum1++;
    }
  }
  sum2 = s[p].size() + s[q].size() - sum1;
  return (sum1*1.0)/(sum2*1.0)*100;
}

int main(){
  int n,t,p,q;
  scanf("%d",&n);
  for(int i = 1; i <= n; i++){
    scanf("%d",&t);
    for(int j = 1; j <= t; j++){
      int temp;
      scanf("%d",&temp);
      s[i].insert(temp);
    }
  }
  scanf("%d",&t);
  while(t--){
    scanf("%d%d",&p,&q);
    printf("%.2lf%%\n",solve(p,q));
    
  }
  return 0;
}

超时的代码

#include<cstdio>
#include<set>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 50 + 5;
int a[maxn][maxn];
set<int> s1,s2;
set<int>::iterator it1;
set<int>::iterator it2;

double solve(int p, int q){
  int sum1 = 0;
  int sum2 = 0;
  s1.clear();
  s2.clear();
  for(int i = 1; i <= a[p][0];i++){
    s1.insert(a[p][i]);
  }
  for(int i = 1; i <= a[q][0];i++){
    s2.insert(a[q][i]);
  }
  for(it1 = s1.begin(); it1 != s1.end(); it1++){
    int p = *it1;;
    if(s2.find(p) != s2.end()){
      sum1++;
    }
  }
  sum2 = s1.size() + s2.size() - sum1;
  return (sum1*1.0)/(sum2*1.0)*100;
}

int main(){
  int n,t,p,q;
  scanf("%d",&n);
  memset(a,-1,sizeof(a));
  for(int i = 1; i <= n; i++){
    scanf("%d",&a[i][0]);
    for(int j = 1; j <= a[i][0] ; j++){
      scanf("%d",&a[i][j]); 
    }
  }
  scanf("%d",&t);
  while(t--){
    scanf("%d%d",&p,&q);
    printf("%.2lf%%\n",solve(p,q));
    
  }
  return 0;
}