【去重+二分查找】集合相似度

╰半橙微兮° 2022-05-30 12:18 116阅读 0赞

Think:  
1.知识点：【去重+二分查找】  
2.题目：  
给定两个整数集合，它们的相似度定义为：Nc/Nt\*100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入格式：  
输入第一行给出一个正整数N（<=50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（<=104），是集合中元素的个数；然后跟M个\[0, 109\]区间内的整数。  
之后一行给出一个正整数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%

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int a[10414];
    int rec[54][10414], num[54];
    
    bool search_x(int b[], int len, int x);
    
    int main(){
        int n, m, k, i, j, q, u, v;
        scanf("%d", &n);
        for(i = 1; i <= n; i++){
            scanf("%d", &m);
            for(j = 0; j < m; j++)
                scanf("%d", &a[j]);
            sort(a, a+m);
            k = 0;
            rec[i][k++] = a[0];
            for(j = 1; j < m; j++){
                if(a[j] != a[j-1])
                    rec[i][k++] = a[j];
            }
            num[i] = k;
        }
        double nc, nt;
        scanf("%d", &q);
        while(q--){
            scanf("%d %d", &u, &v);
            nc = 0;
            for(i = 0; i < num[u]; i++){
                if(search_x(rec[v], num[v], rec[u][i])){
                    nc += 1;
                }
            }
            nt = num[u] + num[v] - nc;
            printf("%.2lf%%\n", nc/nt*100.0);
        }
        return 0;
    }
    bool search_x(int b[], int len, int x){
        int mid, l = 0, r = len-1;
        while(l <= r){
            mid = (l+r)>>1;
            if(b[mid] == x) return true;
            else if(b[mid] < x){
                l = mid+1;
            }
            else {
                r = mid-1;
            }
        }
        return false;
    }