古人云:秀恩爱,分得快。
互联网上每天都有大量人发布大量照片,我们通过分析这些照片,可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人,这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里,他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片,请你分析一对给定的情侣,看看他们分别有没有亲密度更高的异性朋友?
输入格式: 输入在第一行给出 2 个正整数:N(不超过1000,为总人数——简单起见,我们把所有人从 0 到 N-1 编号。为了区分性别,我们用编号前的负号表示女性)和 M(不超过1000,为照片总数)。随后 M 行,每行给出一张照片的信息,格式如下:
其中 K(≤ 500)是该照片中出现的人数,P[1] ~ P[K] 就是这些人的编号。最后一行给出一对异性情侣的编号 A 和 B。同行数字以空格分隔。题目保证每个人只有一个性别,并且不会在同一张照片里出现多次。
输出格式: 首先输出 A PA
,其中 PA
是与 A
最亲密的异性。如果 PA
不唯一,则按他们编号的绝对值递增输出;然后类似地输出 B PB
。但如果 A
和 B
正是彼此亲密度最高的一对,则只输出他们的编号,无论是否还有其他人并列。
输入样例 1: 1 2 3 4 5 6 10 4 4 -1 2 -3 4 4 2 -3 -5 -6 3 2 4 -5 3 -6 0 2 -3 2
输出样例 1:
输入样例 2: 1 2 3 4 5 6 4 4 4 -1 2 -3 0 2 0 -3 2 2 -3 2 -1 2 -3 2
输出样例 2:
思路:
将每一张照片中出现的人编号都存起来,存储过程中顺便判断是否是女性,采用字符串输入编号,因为有可能有-0,若是女性,对其进行标记,方便后续判断性别。
如果将每个人最亲密的异性都存起来,不仅费力,还会超时,所以在输入后,只对这两个人进行查找即可:遍历每一张照片,判断当前照片中是否有要查找编号,若有,则遍历该照片中的人,若性别不同,则该人与输入编号的亲密度增加。
若A B都是彼此亲密度最高的一对,只输出他们两个人的编号,不管其他人的并列,否则都要输出,且按编号绝对值递增输出。
代码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 #include <algorithm> #include <iostream> #include <vector> using namespace std ;int main () { int n, m, k; string s; cin >> n >> m; bool femal[1001 ] = {false }; vector <int > v[m]; for (int i = 0 ; i < m; i++) { cin >> k; for (int j = 0 ; j < k; j++) { cin >> s; string ss = s; if (s[0 ] == '-' ) s = s.substr(1 ); int tmp = stoi(s); if (ss[0 ] == '-' ) femal[tmp] = true ; v[i].push_back(tmp); } } string s1, s2; int a, b; double max1 = 0 , max2 = 0 ; double d1[1001 ] = {0 }, d2[1001 ] = {0 }; cin >> s1 >> s2; if (s1[0 ] == '-' ) { a = stoi(s1.substr(1 )); femal[a] = true ; } else { a = stoi(s1); } if (s2[0 ] == '-' ) { b = stoi(s2.substr(1 )); femal[b] = true ; } else { b = stoi(s2); } for (int i = 0 ; i < m; i++) { if (find (v[i].begin (), v[i].end (), a) != v[i].end ()) { for (int j = 0 ; j < v[i].size (); j++) { if (femal[a] != femal[v[i][j]]) { d1[v[i][j]] += 1.0 / v[i].size (); if (d1[v[i][j]] > max1) max1 = d1[v[i][j]]; } } } if (find (v[i].begin (), v[i].end (), b) != v[i].end ()) { for (int j = 0 ; j < v[i].size (); j++) { if (femal[b] != femal[v[i][j]]) { d2[v[i][j]] += 1.0 / v[i].size (); if (d2[v[i][j]] > max2) max2 = d2[v[i][j]]; } } } } if (max1 == d1[b] && max2 == d2[a]) { cout << s1 << " " << s2; } else { for (int i = 0 ; i < n; i++) { if (max1 == d1[i]) { cout << s1 << " " ; if (femal[i]) cout << "-" << i << endl ; else cout << i << endl ; } } for (int i = 0 ; i < n; i++) { if (max2 == d2[i]) { cout << s2 << " " ; if (femal[i]) cout << "-" << i << endl ; else cout << i << endl ; } } } return 0 ; }