C++ STL set A1063.Set Similarity (注意查询的优化：set数据结构的 find(） 语句 最强大)

 超时主要是这个语句的原因：

　

 for(iter = temp[num1].begin();iter != temp[num1].end();++iter){
            for(iter1 = temp[num2].begin();iter1 != temp[num2].end();++iter1){
                if(*iter == *iter1){
                    t1.insert(*iter);
                }
            }
        }

这个语句可以这样优化：

int totalNum = st[y].size(),sameNum = 0;//不同数的个数，相同数的个数
    //遍历集合st[x]
    for(set<int>::iterator it = st[x].begin();it != st[x].end();++it){
        if(st[y].find(*it) != st[y].end()){//这条语句很厉害！
            sameNum++;
        }else{
            totalNum++;
        }
    }

　

#include <bits/stdc++.h>
#include<math.h>
#include <string>
using namespace std;
const int maxn = 40010;//最大学生人数
int main(){
    int n;
    scanf("%d",&n);
    set<int> temp[n+1];
    for(int i = 1;i<n+1;++i){
        int number;
        scanf("%d",&number);
        for(int j = 0;j<number;++j){
            int num;
            scanf("%d",&num);
            temp[i].insert(num);
        }
    }
    int k;
    scanf("%d",&k);
    double result[k];
    //scanf("%d",&k);
    int num1,num2;
    for(int i=0;i<k;++i){
        set<int> t1;//交集
        set<int> t2;//并集
        scanf("%d%d",&num1,&num2);
        set<int>::iterator iter;
        set<int>::iterator iter1;
        for(iter = temp[num1].begin();iter != temp[num1].end();++iter){
            for(iter1 = temp[num2].begin();iter1 != temp[num2].end();++iter1){
                if(*iter == *iter1){
                    t1.insert(*iter);
                }
            }
        }
        for(iter = temp[num1].begin();iter!=temp[num1].end();++iter){
            t2.insert(*iter);
        }
        for(iter1 = temp[num2].begin();iter1!=temp[num2].end();++iter1){
            t2.insert(*iter1);
        }
        result[i] = t1.size() * 100.0 / t2.size();
    }
    for(int i = 0;i<k;++i){
        printf("%.1f%%
",result[i]);
        //printf("%
");
    }
    system("pause");
    return 0;
} 

---

优化后：

#include <bits/stdc++.h>
#include<math.h>
#include <string>
using namespace std;
const int maxn = 40010;//最大学生人数
const int N = 51;
set<int> st[N];//N个集合
void compare(int x,int y){
    int totalNum = st[y].size(),sameNum = 0;//不同数的个数，相同数的个数
    //遍历集合st[x]
    for(set<int>::iterator it = st[x].begin();it != st[x].end();++it){
        if(st[y].find(*it) != st[y].end()){//这条语句很厉害！
            sameNum++;
        }else{
            totalNum++;
        }
    }
    printf("%.1f%%
",sameNum * 100.0 / totalNum);
}
int main(){
    int n,k,q,v,st1,st2;
    scanf("%d",&n);
    for(int i = 1;i<=n;++i){
        scanf("%d",&k);
        for(int j=0;j<k;++j){
            scanf("%d",&v);//集合i中的元素v
            st[i].insert(v);//将元素v加入集合st[i]中
        }
    }
    scanf("%d",&q);//q个查询
    for(int i = 0;i<q;++i){
        scanf("%d%d",&st1,&st2);//欲对比的集合编号
        compare(st1,st2);
    }
    system("pause");
    return 0;
}