当前位置 : 主页 > 编程语言 > 其它开发 >

2020天梯模拟赛L2-4 秀恩爱分得快

来源:互联网 收集:自由互联 发布时间:2022-05-30
L2-4 秀恩爱分得快 古人云:秀恩爱,分得快。 互联网上每天都有大量人发布大量照片,我们通过分析这些照片,可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人,这些人两

L2-4 秀恩爱分得快
古人云:秀恩爱,分得快。

互联网上每天都有大量人发布大量照片,我们通过分析这些照片,可以分析人与人之间的亲密度。如果一张照片上出现了 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

这道题的思路就是用一个char数组来存进每一个输进来的值,若有‘-’,就令sex数组中对应的值为1,表明其性别,之后通过异或运算来表明双方是不是异性,从而判断是否要加亲密度,我们这里采用一个vector数组来存放照片中的每一个人(存入的是对应的绝对值),再写一个函数来表明情侣双方是不是彼此最亲密的人,如果是就输出,如果不是,就去寻找最亲密的人,因为存入的是绝对值,而且for循环本身就是递增顺序,所以不需要再额外排序。

#include<bits/stdc++.h>
using namespace std;
vector<int> v[1010];
bool sex[1010];
int n,m,k,a,b;
void print(int a,int b)//输出函数 
{
	if(sex[a]) cout<<"-";
	cout<<a<<" ";
	if(sex[b]) cout<<"-";
	cout<<b<<endl;
}
void findmax(int a,int index,double h[])
{
	for(int i=0;i<n;i++)
	{
		if(h[index]==h[i]) print(a,i);
	}
}
bool search(int a,int b,double h[],int &index)//index用来表示亲密值最大的值在数组中的位置,并且是引用参数,会因为函数中的改变而改变 
{
	for(int i=0;i<m;i++)
	{
		index=v[i].size();
		int j;
		for(j=0;j<index;j++)
		{
			if(v[i][j]==a) break;//表明照片中有a
		}
		if(j>=index) continue;
		for(j=0;j<index;j++)
		{
			if(sex[v[i][j]]^sex[a]) h[v[i][j]]+=1.0/index;//这里通过异或运算来表明是异性 
		}
	}
	index=0;
	double maxn=-1;
	for(int i=0;i<n;i++)
	{
		if(maxn<h[i])
		{
			maxn=h[i];
			index=i;
		}
	}
	if(h[b]==h[index]) return 1;//如果b恰好是亲密度最大的,则返回1 
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);//提高cin/cout的效率 
	cin>>n>>m;
	for(int i=0;i<m;i++)
	{
		cin>>k;
		for(int j=0;j<k;j++)
		{
			char c[6];
			cin>>c;
			int temp=abs(atoi(c));//将字符串转化为整数再求绝对值 
			if(c[0]=='-') 
			sex[temp]=1;//方便后面用异或运算来表明是异性关系(=1表示为女生) 
			v[i].push_back(temp);//存储每一张照片的人 
		}
	}
	char ch[6];
	cin>>ch;
	a=abs(atoi(ch));
	if(ch[0]=='-') sex[a]=1;
	cin>>ch;
	b=abs(atoi(ch));
	if(ch[0]=='-') sex[b]=1;
	int ai,bi,isa,isb;//ai,bi表示亲密度最大的值在数组中的位置,isa、isb表示a、b这对情侣是不是对方亲密度最高的人 
	double ha[1010]={},hb[1010]={};//ha数组存放各个异性与a的亲密度,hb存放各个异性与b的亲密度 
	isa=search(a,b,ha,ai);
	isb=search(b,a,hb,bi);
	if(isa&&isb)//如果都是彼此亲密度最大的人,就直接输出 
	{
		print(a,b);
	}
	else//否则就要找到亲密度最大的人进行输出 
	{
		findmax(a,ai,ha);//先输出A,所以先找A最亲密的异性 
		findmax(b,bi,hb);//再找B最亲密的人 
	}
	return 0;
} 

image
image

网友评论