PTA:7-37 秀恩爱分得快 (简洁易懂，详解)
7-37 秀恩爱分得快 (25分)
古人云：秀恩爱，分得快。
互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人，这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？
输入格式：
输入在第一行给出 2 个正整数：N（不超过1000，为总人数——简单起见，我们把所有人从 0 到 N-1 编号。为了区分性别，我们用编号前的负号表示女性）和 M（不超过1000，为照片总数）。随后 M 行，每行给出一张照片的信息，格式如下：
K P[1] … P[K]
其中 K（≤ 500）是该照片中出现的人数，P[1] ~ P[K] 就是这些人的编号。最后一行给出一对异性情侣的编号 A 和 B。同行数字以空格分隔。题目保证每个人只有一个性别，并且不会在同一张照片里出现多次。
输出格式：
首先输出 A PA，其中 PA 是与 A 最亲密的异性。如果 PA 不唯一，则按他们编号的绝对值递增输出；然后类似地输出 B PB。但如果 A 和 B 正是彼此亲密度最高的一对，则只输出他们的编号，无论是否还有其他人并列。
输入样例 1：
10 4
4 -1 2 -3 4
4 2 -3 -5 -6
3 2 4 -5
3 -6 0 2
-3 2
输出样例 1：
-3 2
2 -5
2 -6
输入样例 2：
4 4
4 -1 2 -3 0
2 0 -3
2 2 -3
2 -1 2
-3 2
输出样例 2：
-3 2
思路
考虑题中可能有0，-0的情况，所以定义一个数组sex[]保存，对应编号人的性别。
输入中有m张照片，照片中有k人，这里用动态是数组vector r[]来保存，即r[i]表是第几张照片里面的所有人数。（读者这里不懂的话，可以先去了解一下vector）
接着就会调用函数，将与要查的情侣的异性的亲密度全部保存在ca，cb数组中。然后找最大值。
具体代码解释如下：
#include<bits/stdc++.h>
using namespace std;
vector<int> r[1100]; //r[i]表示第i张照片，里面的元素表示照片中的人
bool sex[1100];
int n,m,k,d,a,b;
void print(int a, int b){
if(sex[a]) cout << "-";
cout << a << " ";
if(sex[b]) cout << "-";
cout << b << endl;
}
//编号从低到高输出，最大值的编号
void print1(int c, double a[], int k){
for(int i=0; i<n; i++){
if(a[i]==a[k]) print(c, i);
}
}
//分别找a,b的亲密度最高的异性。返回值为判断a,b是否为亲密度最高的情侣
bool search(int a, int b, double cn[], int &k){
for(int i=0; i<m; i++){
k = r[i].size();
int j;
for(j=0; j<k; j++){
if(r[i][j]==a) break;
}
if(j>=k) continue; //照片中没有a
for(j=0; j<k; j++){
if(sex[r[i][j]]^sex[a]) cn[r[i][j]] += 1.0/k;
}
}
k=0;
double maxx=-1;
for(int i=0; i<n; i++)
if(cn[i]>maxx){
maxx = cn[i];
k=i;
}
if(cn[b]==cn[k])
return 1;
return 0;
}
int main()
{
char s[10];
cin >> n >> m;
for(int i=0; i<m; i++){
cin >> k;
for(int j=0; j<k; j++){
cin >> s;
int t = abs(atoi(s));
if(s[0]=='-')sex[t]=1; //如果为女性将对应标号的Sex[]置为1
r[i].push_back(t);
}
}
cin >> s;
a = abs(atoi(s));
if(s[0]=='-')sex[a]=1;
cin >> s;
b = abs(atoi(s));
if(s[0]=='-')sex[b]=1;
int c,d,e,f; //c,d表示最大值在亲密度ca,cb数组中的位置（即函数中的k，注意k是引用，所以c,d的值会跟着变化）
double ca[1100]={},cb[1100]={}; //ca存储与a的异性的亲密度，cb是与b的异性的亲密度
e = search(a,b,ca,c);
f = search(b,a,cb,d);
if(e&&f)print(a,b);
else{
print1(a,ca,c);
print1(b,cb,d);
}
return 0;
}
欢迎大家批评改正，积极讨论，让我们共同进步，加油！！！