1063 Set Similarity (25 分)

Given two sets of integers, the similarity of the sets is defined to be N c / N t × 100 N_c/N_t×100 Nc​/Nt​×100​%, where N c N_c Nc​​​ is the number of distinct common numbers shared by the two sets, and N t N_t Nt​​​ is the total number of distinct numbers in the two sets. Your job is to calculate the similarity of any given pair of sets.

Input Specification:

Each input file contains one test case. Each case first gives a positive integer N (≤50) which is the total number of sets. Then N lines follow, each gives a set with a positive M ( ≤ 1 0 4 ≤10^4 ≤104) and followed by M integers in the range [0, 1 0 9 10^9 109]. After the input of sets, a positive integer K (≤2000) is given, followed by K lines of queries. Each query gives a pair of set numbers (the sets are numbered from 1 to N). All the numbers in a line are separated by a space.

Output Specification:

For each query, print in one line the similarity of the sets, in the percentage form accurate up to 1 decimal place.

Sample Input:

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

Sample Output:

50.0%
33.3%

解释:

输入集合总数N

然后接下来N行输入集合,包括集合包元素数,和集合内各个元素

然后输入M个查询,每次输入两个集合序号(1-N)

输出集合的交并比=交集元素个数/并集元素个数*100%,每个元素要去重

#include<cstdio>
#include<set>
using namespace std;
const int N=51;
//定义一个集合的数组
set<int> st[N];
void compare_set(int x,int y)
{
    int totaNum=st[y].size(),samenum=0;
    for(set<int> ::iterator it=st[x].begin();it!=st[x].end();it++)//迭代器访问set中各个元素
    {
        //找到一样的,交集元素个数
        if(st[y].find(*it)!=st[y].end())
            samenum++;
        //并集元素个数++
        else
            totaNum++;
    }
    printf("%.1f%\n",samenum*100.0/totaNum);
}
int main()
{
    int n,k,v,q;
    int st1,st2;
    //输入·set总数
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&k);//输入当前set元素总数
        for(int j=0;j<k;j++)
        {
            scanf("%d",&v);
            st[i].insert(v);//输入到set[i]中
        }
    }
    //输入查询总数
    scanf("%d",&q);
    for(int i=0;i<q;i++)
    {
        scanf("%d %d",&st1,&st2);
        compare_set(st1,st2);
    }
    return 0;
}
/*
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
*/
上一篇:1063:最大跨度值


下一篇:1063 计算谱半径 (20 分)