[PAT A1063]Set Similarity
题目描述
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.
输入格式
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 (≤) and followed by M integers in the range [0,
]. 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.
输出格式
For each query, print in one line the similarity of the sets, in the percentage form accurate up to 1 decimal place.
输入样例
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
输出样例
50.0%
33.3%
解析
本题不算是一道很难的题，主要是考察STL中的set的使用，如果会使用set工具的话，那么就会减少很多的麻烦。题目的大概意思是，首先输入一个数N，表示有N个set，然后对于每个set，输入set的元素的个数和每个元素的值（注意，这里元素的个数并不是set真正元素的个数，因为集合set具有互斥性，即一个集合set中不能出现多个相同的值得元素），然后定义了一个值叫做similarity（相似度），就是两个set交集中的元素个数除以两个set并集的元素个数。
#include<iostream>
#include<set>
using namespace std;
const int maxn = 50;//最大的集合数
int main()
{int n;scanf("%d", &n);set<int> s[maxn + 1];for (int i = 1; i <= n; i++) {int num, temp; //元素的个数和当前元素的值scanf("%d", &num);for (int j = 0; j < num; j++) {scanf("%d", &temp);s[i].insert(temp); //把输入的元素插入到set中去}}int q_num; //这里是需要查询的set对个数scanf("%d", &q_num);for (int i = 0; i < q_num; i++) {int a, b, count = 0;scanf("%d%d", &a, &b);set<int>::iterator p = s[a].begin(), q = s[b].begin();while (p != s[a].end() && q != s[b].end()) { //这里我是自己想的，类似于two pointer思想吧if (*p == *q) {p++; q++;count++;}else if (*p > *q)q++;else p++;}int sum = s[a].size() + s[b].size() - count;double rate = (double)count / sum; //计算比例rate *= 100;printf("%.1f", rate);cout << "%" << endl;}return 0;
}