PAT甲级-1063 Set Similarity (25分)_综合

点击链接PAT甲级-AC全解汇总

题目：
Given two sets of integers, the similarity of the sets is defined to be N_?c?? /N_?t?? ×100%, where N_?c?? is the number of distinct common numbers shared by the two sets, and N_?t?? 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 (≤10^?4?? ) and followed by M integers in the range [0,10^?9?? ]. 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%

题意：
输入一堆集合，求查询的两个集合的相似度，即 $交集元素的个数并集元素的个数\frac{交集元素的个数}{并集元素的个数}$ ；

我的思路：
对于集合a，b，遍历a，如果b中有对应的元素，那么交集个数从0开始++，如果b中没有对应的元素，那么并集个数从b的个数起++

我的代码：

#include<bits/stdc++.h>
using namespace std;
double similarity(set<int>&a ,set<int>&b){
    int Union=b.size(),Intersection=0;for(auto x:a){
    if(b.find(x)!=b.end())Intersection++;else Union++;}return 100.0*Intersection/Union;
}
int main()
{
    int N;cin>>N;vector<set<int> >sets;for(int i=0;i<N;i++){
    int cnt;cin>>cnt;set<int>set_t;for(int j=0;j<cnt;j++){
    int t;cin>>t;set_t.insert(t);}sets.push_back(set_t);}cin>>N;for(int i=0;i<N;i++){
    int a,b;cin>>a>>b;printf("%.1f%\n",similarity(sets[a-1],sets[b-1]));}return 0;
}