# 7-9 set similarity (25 points)

Given two sets of integers, their similarity is defined as N c / n t × 100%. Where N c is the number of unequal integers in both sets, n t is the number of unequal integers in both sets. Your task is to calculate the similarity of any given set.
Input format:

Input the first line to give a positive integer N (≤ 50), which is the number of sets. Then N lines, each corresponding to a set. Each set first gives a positive integer m (< 10 4), which is the number of elements in the set; then it is followed by an integer in M [0,10 9] intervals.

The next line gives a positive integer k (≤ 2000), and then the K line corresponds to the number of a pair of sets (sets from 1 to N) that need to calculate the similarity. Numbers are separated by spaces.
Output format:

For each pair of sets that need to be calculated, their similarity is output in a row, which is a percentage number of two decimal places.
Input example:

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

Output example:

50.00%
33.33%

Idea: set a two-dimensional array. a[i][0] represents the number of each group. When entering a group, sort it, and then perform a duplicate check. During the duplicate check, update the duplicate elements to 1e10 (because the maximum number range is 1e9) and count them. After the duplicate is removed, sort them again. Then subtract the number of duplicate elements from a[i][0]. At this time, a[i][0] represents the non duplicate elements Number.

```#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
long long a[55][10005];
int cnt,sum;
void slove(long long a[],long long n,long long b[],long long m)
{
int i=1,j=1;

while(i<=n&&j<=m)
{
if(b[j]<a[i])
{
sum++;//sum records the number of different elements in two sets
j++;
}
else if(a[i]<b[j])
{
sum++;
i++;
}
else if(a[i] == b[j])
{
sum++;
cnt++;//cnt records the same number of elements in two sets
i++;
j++;
}
}
if(i<=n) sum += n-i+1;//The first set still has a surplus (the reason why the length of two sets can't be reduced is that, for example, 4599 100 101, 4599 101 135, in the end, I and j all point to 101, but there is another 135 that hasn't been added)
if(j<=m) sum += m-j+1;//The second set has the rest
}
int main()
{
int n,k,x,y;
long long i,j;
scanf("%d",&n);
int sum1;

for(i=1;i<=n;i++)
{
sum1 = 0;
scanf("%lld",&a[i][0]);
for(j=1;j<=a[i][0];j++)
{
scanf("%lld",&a[i][j]);
}
sort(a[i]+1,a[i]+1+a[i][0]);
for(j=1;j<a[i][0];j++)
{
if(a[i][j]==a[i][j+1])
{
a[i][j] = 1e10;
sum1 ++;

}
}
sort(a[i]+1,a[i]+1+a[i][0]);
a[i][0] -= sum1;
}
scanf("%d",&k);
while(k--)
{
scanf("%d %d",&x,&y);
cnt = sum = 0;
slove(a[x],a[x][0],a[y],a[y][0]);
double ans = cnt*1.0/sum;
printf("%.2lf%c\n",ans*100,'%');
}
return 0;
}
```

Keywords: REST

Added by jbachris on Thu, 02 Apr 2020 19:26:21 +0300