【GPLT】L2-005 集合相似度

正文索引 [隐藏]

题目描述:

给定两个整数集合,它们的相似度定义为:N​c​​/N​t​​×100%。其中N​c​​是两个集合都有的不相等整数的个数,N​t​​是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入描述:

输入第一行给出一个正整数N(≤50),是集合的个数。随后N行,每行对应一个集合。每个集合首先给出一个正整数M(≤10​4​​),是集合中元素的个数;然后跟M个[0,10​9​​]区间内的整数。

之后一行给出一个正整数K(≤2000),随后K行,每行对应一对需要计算相似度的集合的编号(集合从1到N编号)。数字间以空格分隔。

输出描述:

对每一对需要计算的集合,在一行中输出它们的相似度,为保留小数点后2位的百分比数字。

输入样例:

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

输出样例:

50.00%
33.33%

解题思路:

我一开始的思路很简单粗暴,就是把每个集合中的元素放入相应的set数组中,然后无脑for-each找出俩个集合中共有的元素个数Nc,根据Nc再算出Nt,从而可以输出结果Nc/Nt*100%。可是在我提交代码之后,有个测试用例TLE了。天真的我以为只要再加上一行ios::sync_with_stdio(false);取消cin和stdin的同步之后就能够避免超时直接AC啦。然而提交之后还是TLE,问了一下学长,他说双层for循环导致的超时,求俩个set中交集可以用到一个函数叫set_intersection()。这个函数有5个参数,分别是:set1.begin(),set1.end(),set2.begin(),set2.end(),back_inserter(vector)。back_inserter()函数是iterator适配器,它能使元素被插入到作为实参的某种容器的尾部。这样就可以直接用Nc = vector.size()来代替原来的那俩层for-each语句啦,提交代码全部AC。tql!

AC代码:TLE代码:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    int N;
    cin >> N;     //集合个数
    set<int> s[N+1];
    for(int i = 1; i <= N; i++)
    {
        int M;
        cin >> M;
        for(int j = 0; j < M; j++)
        {
            int temp;
            cin >> temp;
            s[i].insert(temp);
        }
    }
    int K;
    cin >> K;
    for(int i = 0; i < K; i++)
    {
        int x,y;
        int Nc = 0;    //Nc是两个集合都有的不相等整数的个数
        cin >> x >> y;
        for(auto a : s[x])
        {
            for(auto b : s[y])
            {
                if(a == b)
                {
                    Nc++;
                }
            }
        }
        int Nt = s[x].size()+s[y].size()-Nc;  //Nt是两个集合一共有的不相等整数个数
        double temp = (double)Nc/Nt*100;
        printf("%.2f%%\n",temp);
    }
    return 0;
}

AC代码:

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    int N;
    cin >> N;     //集合个数
    set<int> s[N+1];
    for(int i = 1; i <= N; i++)
    {
        int M;
        cin >> M;
        for(int j = 0; j < M; j++)
        {
            int _;
            cin >> _;
            s[i].insert(_);
        }
    }
    int K;
    cin >> K;
    for(int i = 0; i < K; i++)
    {
        int x,y;
        cin >> x >> y;
        vector<int> v;
        set_intersection(s[x].begin(),s[x].end(),s[y].begin(),s[y].end(),back_inserter(v));  //set求交集
        int Nc = v.size();    //Nc是两个集合都有的不相等整数的个数
        int Nt = s[x].size()+s[y].size()-Nc;  //Nt是两个集合一共有的不相等整数个数
        double ans = (double)Nc/Nt*100;
        printf("%.2f%%\n",ans);
    }
    return 0;
}