PAT1063

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<map>
 4 #include<vector>
 5 #include<iomanip>
 6 #include<iterator>
 7 using namespace std;
 8 
 9 double similary(map<int, vector<int>> &check, int a, int b)
10 {
11     double common(0);
12     vector<int>::iterator itera = check[a].begin(), iterb=check[b].begin();
13     while(itera != check[a].end() && iterb != check[b].end())
14     { 
15         if(*itera == *iterb)
16         {
17             ++common;
18             ++itera; ++iterb;
19         }
20         else if(*itera < *iterb)
21             ++itera;
22         else
23             ++iterb;
24     }
25     return common/(double)( check[a].size()+check[b].size()-common);
26 }
27 
28 int main()
29 {
30     int N;
31     while(scanf("%d", &N) != -1)
32     {
33         map<int, vector<int>> check;
34         for(int i=0; i<N; ++i)
35         {
36             int M; scanf("%d", &M);
37             vector<int> temp(M);
38             for(int j=0; j<M; ++j)
39                 scanf("%d", &temp[j]);
40             sort(temp.begin(), temp.end());
41             vector<int> v1(temp.begin(), unique(temp.begin(), temp.end()));
42             check[i] = v1;
43         }
44         int L;  scanf("%d", &L);
45         vector<double> outcome(L);
46         for(int i=0; i<L; ++i)
47         {
48             int a, b;  scanf("%d%d", &a, &b);
49             outcome[i]=similary(check, a-1, b-1);
50         }
51         for(int i=0; i<L; ++i)
52             printf("%.1f%%
", outcome[i]*100);
53     }
54 }

题目链接：http://pat.zju.edu.cn/contests/pat-a-practise/1063

题目不难：一开始用的set自动去重复，超时了，后来改用用sort()下， unique()去重下，在自己写个函数判断有多少相同元素。最后一个case130ms。

改成scanf printf最后一个case110ms。