L2-005 集合相似度

PTA 模拟 C++ 所有文稿

关键词：集合超时

/*10:42-10:55 最后一个测试超时*/
#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
#include <cstdio>
using namespace std;
const int maxn=55;
int n;
set<long long> a[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        long long m,x;
        cin>>m;
        for(int j=0;j<m;j++){
            cin>>x;
            (a[i]).insert(x);
        }
    }
    int k;
    cin>>k;
    for(int i=0;i<k;i++){
        int x,y,sn=0,tn=0;
        cin>>x>>y;
        //set<long long> s,t; 第二次修改为用两个集合分别存数，在计算size，也超时了
        for(auto it=a[x].begin();it!=a[x].end();it++){//这次直接算数 全通过了
            if (a[y].count(*it)) sn++;
        }
        //for(auto it=a[y].begin();it!=a[y].end();it++) t.insert(*it);
/*
一开始使用的函数，超时了
set_union(a[x].begin(),a[x].end(),a[y].begin(),a[y].end(),inserter(t,t.begin()));   set_intersection(a[x].begin(),a[x].end(),a[y].begin(),a[y].end(),inserter(s,s.begin()));
*/
        float r=1.0*sn/(a[x].size()+a[y].size()-sn)*100;
        printf("%.2f%%\n",r);
    }
    system("pause");
    return 0;
}

2019.3.17