欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA:7-37 秀恩爱分得快 (简洁易懂,详解)

程序员文章站 2022-03-13 16:46:17
...

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;
}

PTA:7-37 秀恩爱分得快 (简洁易懂,详解)
欢迎大家批评改正,积极讨论,让我们共同进步,加油!!!