1063 Set Similarity (25分)

题目

Given two sets of integers, the similarity of the sets is defined to be Nc/Nt×100%N_c/N_t\times100\%Nc​/Nt​×100%, where NcN_cNc​ is the number of distinct common numbers shared by the two sets, and NtN_tNt​ 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)N(\le50)N(≤50) which is the total number of sets. Then N lines follow, each gives a set with a positive M(104)M(\le10^4)M(≤104) and followed by M integers in the range [0,109][0,10^9][0,109]. After the input of sets, a positive integer K(2000)K(\le2000)K(≤2000) is given, followed by KKK lines of queries. Each query gives a pair of set numbers (the sets are numbered from 111 to NNN). 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%

题目大意

给出两个集合数据,NcN_cNc​表示两个集合中相同的元素,NtN_tNt​表示两个集合总的不相同元素的个数,求Nc/NtN_c/N_tNc​/Nt​。

思路

首先题目要对集合去重,这里可以直接用set实现,并且set内部自动实现排序,后面统计数据会更方便,统计Nc,NtN_c,N_tNc​,Nt​可以用两个指针实现,具体见代码。

代码

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;

bool cmp(int a, int b){
    return a < b;
}

int main(){
    int n, k;
    set<int> sets[51];
    scanf("%d", &n);
    for(int i=1, t; i<=n; i++){
        scanf("%d", &t);
        for(int j=0, c; j<t; j++){
            scanf("%d", &c);
            sets[i].insert(c);
        }
    }
    scanf("%d", &k);
    while(k--){
        int s, t, nc = 0, nt = 0;
        scanf("%d%d", &s, &t);
        set<int>::iterator it1 = sets[s].begin(), it2 = sets[t].begin();
        while(it1 != sets[s].end() && it2 != sets[t].end()){
            if(*it1 > *it2)
                nt++, it2++;
            else if(*it1 == *it2)
                nt++, nc++, it1++, it2++;
            else
                nt++, it1++;
        }
        while(it1 != sets[s].end())
            nt++, it1++;
        while(it2 != sets[t].end())
            nt++, it2++;
        printf("%.1f%%\n", (nc*1.0)/nt*100);
    }
    return 0;
}
1063 Set Similarity (25分)1063 Set Similarity (25分) 李小白~ 发布了73 篇原创文章 · 获赞 35 · 访问量 1万+ 私信 关注
上一篇:PAT basic 1063 计算谱半径 (20分) C++


下一篇:1063 计算谱半径