PAT A组1063题（Set Similarity）

题目描述

Given two sets of integers, the similarity of the sets is defined to be Nc/Nt×100%, where Nc is the number of distinct common numbers shared by the two sets, and 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 (≤104) and followed by M integers in the range [0,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.

（集合删除各自重复个数后，求交集个数除以并集个数）

思路&代码实现

一开始的思路很简单，用set各自去重，然后记录两个集合的元素个数之和total；将两个集合合并（调用成员函数set.insert)，记录并集个数Nt，交集个数Nc即是total-Nt。

上述思路对应代码

#include <set>
#include <cstdio>
using namespace std;
int main()
{
    set<int> seq[51];
    int N, M;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &M);
        int number;
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &number);
            seq[i].insert(number);
        }
    }
    int K, Nc, Nt, total;
    scanf("%d", &K);
    for (int i = 0; i < K; i++)
    {
        int id1, id2;
        scanf("%d %d", &id1, &id2);
        total = seq[id1].size() + seq[id2].size();
        seq[id2].insert(seq[id1].begin(), seq[id1].end());
        Nt = seq[id2].size();
        Nc = total - Nt;
        printf("%.1f%%\n", Nc * 100.0 / Nt);
    }
    return 0;
}

然而不知道为什么，vscode以及测试用例都过了，答案是不对的。不过上述代码最后一个测试点也超时了，测试非零返回发现数据确实大，将cin改为scanf依然过不了。

修改思路及AC代码

于是可能的原因是insert的步骤导致的超时，那么换以下思路。现将并集个数Nt设为set1的个数，交集个数Nc清0；再在set1中查找set2的元素，能找到则Nc++，不能找到则Nt++。
set成员函数find的返回值：

Return value

An iterator to the element, if val is found, or set::end otherwise.

所以find返回set1::end则说明没找到set2的元素，于是代码如下。

AC代码

#include <set>
#include <cstdio>
using namespace std;
int main()
{
    set<int> seq[51];
    int N, M;
    scanf("%d", &N);
    for (int i = 1; i <= N; i++)
    {
        scanf("%d", &M);
        int number;
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &number);
            seq[i].insert(number);
        }
    }
    int K, Nc, Nt;
    scanf("%d", &K);
    for (int i = 0; i < K; i++)
    {
        int id1, id2;
        scanf("%d %d", &id1, &id2);
        Nc = 0;
        Nt = seq[id1].size();
        for (set<int>::iterator it = seq[id2].begin(); it != seq[id2].end(); it++)
        {
            if (seq[id1].find(*it) != seq[id1].end())
                Nc++;
            else
                Nt++;
        }
        printf("%.1f%%\n", (Nc * 100.0) / (Nt * 1.0));
    }
    return 0;
}