专栏首页Don的成长史【GPLT】L2-005 集合相似度

【GPLT】L2-005 集合相似度

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/weixin_42449444/article/details/88556720

题目描述:

给定两个整数集合,它们的相似度定义为: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 temp;
            cin >> temp;
            s[i].insert(temp);
        }
    }
    int K;
    cin >> K;
    for(int i = 0; i < K; i++)
    {
        int x,y;
        cin >> x >> y;
        vector<int> res;
        set_intersection(s[x].begin(),s[x].end(),s[y].begin(),s[y].end(),back_inserter(res));  //set求交集
        int Nc = res.size();    //Nc是两个集合都有的不相等整数的个数
        int Nt = s[x].size()+s[y].size()-Nc;  //Nt是两个集合一共有的不相等整数个数
        double temp = (double)Nc/Nt*100;
        printf("%.2f%%\n",temp);
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【CCF】相邻数对

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • HBU-DS2018SY-1-1 数组循环左移 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 【PAT乙级】数组元素循环右移问题

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • poj-1218 THE DRUNK JAILER 喝醉的狱卒

    就是一个狱卒喝醉了,他第一趟吧所有的监狱都带开,第二趟把能把二整除的监狱关闭,第三趟操作能把三整除的监狱;

    瑾诺学长
  • 05:Cave Cows 1 洞穴里的牛之一

    总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 很少人知道其实奶牛非常喜欢到洞穴里面去探险。     洞窟里有N...

    attack
  • Java实现图片的滤镜效果滤镜实现总结

    在移动端或者在web开发时处理图片都是一件麻烦的事儿。我调研过很多library,特别是在移动端处理图片时动不动都需要使用 C++ 或者 OpenCV。这对于 ...

    fengzhizi715
  • 1072 开学寄语 (20 分)

    可爱见见
  • 1061 判断题 (15 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 洛谷P1437 [HNOI2004]敲砖块(dp)

    在一个凹槽中放置了 n 层砖块、最上面的一层有n 块砖,从上到下每层依次减少一块砖。每块砖

    attack
  • 【CCF】相邻数对

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk

扫码关注云+社区

领取腾讯云代金券