【Patest】集合相似度（二分）

FishWang

发布于 2025-08-27 12:14:38

6200

代码可运行

运行总次数：0

代码可运行

集合相似度 (25分) 给定两个整数集合，它们的相似度定义为：N_c / N_t \times 100\%N c /N t ×100%。其中N_cN c 是两个集合都有的不相等整数的个数，N_tN t 是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。输入格式：

输入第一行给出一个正整数NN（\le 50≤50），是集合的个数。随后NN行，每行对应一个集合。每个集合首先给出一个正整数MM（\le 10^4≤10 4 ），是集合中元素的个数；然后跟MM个[0, 10^9][0,10 9 ]区间内的整数。之后一行给出一个正整数KK（\le 2000≤2000），随后KK行，每行对应一对需要计算相似度的集合的编号（集合从1到NN编号）。数字间以空格分隔。输出格式：

对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后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%

对于给出的数组先排序后去重，然后对于每次查找用二分查找。

代码如下：

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define For(x,n) for(int x=1;x<=n;x++)
int num[55][10000+5];
int main()
{
    int n;
    cin >> n;
    For(i,n)
    {
        cin >> num[i][0];
        For(j,num[i][0])
            cin >> num[i][j];
        sort(num[i]+1,num[i]+1+num[i][0]);
        num[i][0] = unique(num[i]+1,num[i]+1+num[i][0]) - num[i] - 1;
    }
    int k;
    int x,y;
    cin >> k;
    while (k--)
    {
        cin >> x >> y;
        int ant = 0;
        For(i,num[x][0])
        {
            if (num[x][i] == *(upper_bound(num[y]+1,num[y]+1+num[y][0],num[x][i]) - 1))
                ant++;
        }
//        cout << (double)ant/(num[x][0]+num[y][0]-ant) << endl;
        printf ("%.2lf%\n",(double)ant/(num[x][0]+num[y][0]-ant)*100.0);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

集合