[PAT解题报告] Set Similarity
简单题,集合求交。正规做法是用数组存好,排好顺序,用O(n)的归并方法求交。
我直接用了C++ STL的set存了所有的集合,求交就不用排序了,用iterator迭代就可以了。求交的方法就是哪个iterator对应的数小,就移动哪个,如果相等就找到了一个相交的元素。当然还要算一下并集元素的个数,因为要算相似度,用交集元素个数除以并集元素个数。
#include <set>
#include <cstdio>

using namespace std;

set<int> a[52];

double give(int x,int y) {
int inter = 0, total = 0;
    for (set<int>::iterator t1 = a[x].begin(), t2 = a[y].begin(); (t1 != a[x].end()) ||  (t2 != a[y].end()); ++total) {
        if (t1 == a[x].end()) {
            ++t2;
        }
        else if (t2 == a[y].end()) {
            ++t1;
        }
        else if (*t1 == *t2) {
            ++inter;
            ++t1;
            ++t2;
        }
        else if (*t1 < *t2) {
            ++t1;
        }
        else {
            ++t2;
        }
    }
    return inter * 100.0 / total;
}

int main() {
int n;
    scanf("%d",&n);
    for (int i = 0; i < n; ++i) {
        int x;
        for (scanf("%d",&x);x;--x) {
            int y;
            scanf("%d",&y);
            a[i].insert(y);
        }
    }
    int m;
    for (scanf("%d",&m);m;--m) {
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%.1lf%%\n", give(x - 1,y - 1));
    }
    return 0;
}



原题链接: http://www.patest.cn/contests/pat-a-practise/1063

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-20 00:05
门头沟学院_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-28 02:13
门头沟学院_2024
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议