L2-028 秀恩爱分得快

小咪咪 2022-03-16 12:13 148阅读 0赞

L2-028 秀恩爱分得快 （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的情况，所以一定要%s输入判断了，然后开个sex数组记录一下性别

还要注意如果询问的两个人均没有出现在照片上时，性别没有被记录，所以要单独处理。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int sex[1005];//性别
    vector<int> ma[1005];//存照片 
    double pa[1005],pb[1005];//存亲密度 
    int f(char s[])
    {
        int n=0;
        if(s[0]=='-')
        {
            for(int i=1;i<strlen(s);i++)
            n=n*10+s[i]-'0';
        }
        else
        {
            for(int i=0;i<strlen(s);i++)
            n=n*10+s[i]-'0';
        }
        return n;
    }
    int main()
    {
    	int n,m,k,i,j,x,y;
    	char c[5],cx[5],cy[5];
    	memset(sex,0,sizeof sex);	
    	memset(pa,0,sizeof pa);
    	memset(pb,0,sizeof pb);
    	scanf("%d%d",&n,&m);
    	for(i=0;i<m;i++)
    	{
    		scanf("%d",&k);
    		for(j=0;j<k;j++)
    		{
    			scanf("%s",c);
                ma[i].push_back(f(c));
                if(c[0]=='-')
    			sex[f(c)]=1;//1女0男 
    		}
    	}
    	scanf("%s%s",&cx,&cy);
    	x=f(cx);
    	y=f(cy);
    	double maxx=0,maxy=0;
    	for(i=0;i<m;i++) 
    	{
    		bool fx=find(ma[i].begin(),ma[i].end(),x)!=ma[i].end();	
    		bool fy=find(ma[i].begin(),ma[i].end(),y)!=ma[i].end();	
    		if(fx||fy) 
    		{
    			for(j=0;j<ma[i].size();j++) 
    			{
    				if(fx&&sex[x]!=sex[ma[i][j]])//找到了x且两者性别不同 
    				{
    					pa[ma[i][j]]+=1.0/ma[i].size();
    					maxx=max(maxx,pa[ma[i][j]]);
    				}
    				if(fy&&sex[y]!=sex[ma[i][j]]) 
    				{
    					pb[ma[i][j]]+=1.0/ma[i].size();
    					maxy=max(maxy,pb[ma[i][j]]);
    				}
    			}
    		}
    	}
    	if(maxx==pa[y]&&maxy==pb[x]&&maxx==0&&maxy==0)
    	printf("%s %s\n",cx,cy);//没有这个只有23分，少一个测试点 
     	else if(maxx==pa[y]&&maxy==pb[x])
     	printf("%s%d %s%d\n",sex[x]?"-":"",x,sex[y]?"-":"",y);
     	else
     	{
    	 	for(i=0;i<n;i++)
    	 	{
    	 		if(maxx==pa[i])
    	 		printf("%s%d %s%d\n",sex[x]?"-":"",x,sex[i]?"-":"",i);
    	 	}
    	 	for(i=0;i<n;i++)
    	 	{
    	 		if(maxy==pb[i])
    	 		printf("%s%d %s%d\n",sex[y]?"-":"",y,sex[i]?"-":"",i);
    	 	}
    	}
    }