L2-044 大众情人分数 25分

人与人之间总有一点距离感。我们假定两个人之间的亲密程度跟他们之间的距离感成反比,并且距离感是单向的。例如小蓝对小红患了单相思,从小蓝的眼中看去,他和小红之间的距离为 1,只差一层窗户纸;但在小红的眼里,她和小蓝之间的距离为 108000,差了十万八千里…… 另外,我们进一步假定,距离感在认识的人之间是可传递的。例如小绿觉得自己跟小蓝之间的距离为 2,则即使小绿并不直接认识小红,我们也默认小绿早晚会认识小红,并且因为跟小蓝很亲近的关系,小绿会觉得自己跟小红之间的距离为 1+2=3。当然这带来一个问题,如果小绿本来也认识小红,或者他通过其他人也能认识小红,但通过不同渠道推导出来的距离感不一样,该怎么算呢?我们在这里做个简单定义,就将小绿对小红的距离感定义为所有推导出来的距离感的最小值。

一个人的异性缘不是由最喜欢他/她的那个异性决定的,而是由对他/她最无感的那个异性决定的。我们记一个人 i 在一个异性 j 眼中的距离感为 Dij​;将 i 的“异性缘”定义为 1/maxj∈S(i)​{Dij​},其中 S(i) 是相对于 i 的所有异性的集合。那么“大众情人”就是异性缘最好(值最大)的那个人。

本题就请你从给定的一批人与人之间的距离感中分别找出两个性别中的“大众情人”。

输入格式:

输入在第一行中给出一个正整数 N(≤500),为总人数。于是我们默认所有人从 1 到 N 编号。

随后 N 行,第 i 行描述了编号为 i 的人与其他人的关系,格式为:

性别 K 朋友1:距离1 朋友2:距离2 …… 朋友K:距离K

其中 性别 是这个人的性别,F 表示女性,M 表示男性;K(<N 的非负整数)为这个人直接认识的朋友数;随后给出的是这 K 个朋友的编号、以及这个人对该朋友的距离感。距离感是不超过 106 的正整数。

题目保证给出的关系中一定两种性别的人都有,不会出现重复给出的关系,并且每个人的朋友中都不包含自己。

输出格式:

第一行给出自身为女性的“大众情人”的编号,第二行给出自身为男性的“大众情人”的编号。如果存在并列,则按编号递增的顺序输出所有。数字间以一个空格分隔,行首尾不得有多余空格。

输入样例:

6
F 1 4:1
F 2 1:3 4:10
F 2 4:2 2:2
M 2 5:1 3:2
M 2 2:2 6:2
M 2 3:1 2:5

输出样例:

2 3
4

代码长度限制

16 KB

Java (javac)

时间限制

1200 ms

内存限制

128 MB

其他编译器

时间限制

400 ms

内存限制

64 MB

思路:floyd()算法没啥说的,暂时没别的办法了。

坑点:知道是“对他/她最无感的那个异性决定的”就行了,后面那一串公式就是用来你的,是不是感觉表述不清楚,还在吐槽题目……………………,

              对他/她最无感的异性,那就是==所有异性眼中,距离他/她最远的那个值决定的,不用管那个值是多少,反正距离最远就对了

若g[i][j]表示 i 对 j 的距离, 那么需要找的应该是所有异性 g[j][i]的值中最大的那一个作为 i 的异性缘指标,

        然后假设有 s 个女性 / 男性 ,还得从 s 个指标中找最小的那一个是属于谁的,谁才是大众情人

 

#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=505;

vector<int>F,M;
queue<int>que;
int g[N][N];


int solve(int n){   
	//floyd算法 
	for(int k=1;k<=n;k++)
	for(int i=1;i<=n;i++)
	for(int j=1;j<=n;j++)
	g[i][j]=min(g[i][j],g[i][k]+g[k][j]);

//查看数据	
//	for(int i=1;i<=n;i++){
//		cout<<"   "<<FM[i]<<i<<"  ";
//	for(int j=1;j<=n;j++) printf("%5d  ",g[i][j]);
//	cout<<endl;	
//	}

	//女生大众情人 
	int min_D=INF;
	for(int i=0;i<F.size();i++){
		int Dij=0;
		for(int j=0; j<M.size(); j++){//寻找所有男性眼中她是最远的那个值 
			Dij=max(Dij,g[M[j]][F[i]]);				
//			printf("   D%d%d=%-3d",M[j],F[i],g[M[j]][F[i]]);
		}
//		cout<<"--> 女"<<F[i]<<" : "<<Dij<<endl;
		if(Dij<min_D){
			min_D=Dij;
			while (!que.empty()) que.pop();	
			que.push(F[i]); 
		} 									
		else if( Dij==min_D)  que.push(F[i]);	
	}	
	
	if(!que.empty()){  cout<<que.front();	que.pop(); }			
	while(!que.empty()) { cout<<" "<<que.front();	que.pop(); }
	cout<<endl;
		
	//男生大众情人 
	int max_D=INF;
	for(int i=0;i<M.size();i++){
		int Dij=0;
		for(int j=0; j<F.size(); j++){//寻找所有男性眼中她是最远的那个值 
			Dij=max(Dij,g[F[j]][M[i]]);				
//			printf("   D%d%d=%-3d",F[i],M[j],g[F[j]][M[i]]);
		}
//		cout<<"  男"<<M[i]<<" : "<<Dij<<endl;
		
		if(Dij<max_D){
			max_D=Dij;
			while (!que.empty()) que.pop();	
			que.push(M[i]); 
		} 									
		else if( Dij==max_D)  que.push(M[i]);	
	}	
	
	if(!que.empty()){  cout<<que.front();	que.pop(); }		
	while(!que.empty()) { cout<<" "<<que.front();	que.pop(); }
	cout<<endl;	
}

int main(){
	//cin.tie(0)->sync_with_stdio(false); cout.tie(0);
	memset(g,INF,sizeof g);
	int n,k,j,dis;	
	char fm; 
	cin>>n;
	for(int i=1;i<=n;i++){
		g[i][i]=0;	
		cin>>fm>>k;
		if(fm=='F')	F.push_back(i);
		else 	M.push_back(i); 
		while(k--) { 
			scanf("%d:%d",&j,&dis); 
			g[i][j]=dis; 
		}		
	}
	solve(n);
	return 0;
} 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/12178.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

36岁大龄程序员被裁,找了2个月工作,年包从100万降到50万,要不要接?

为了找到工作&#xff0c;你愿意接受降薪多少&#xff1f; 一位36岁的杭州程序员问&#xff1a; 36岁被裁&#xff0c;找了2个月工作&#xff0c;年包从100万降到50万&#xff0c;真心纠结&#xff0c;要不要接&#xff1f; 网友们分成了旗帜鲜明的两派&#xff0c;一派人认为不…

【面试题】20个常见的前端算法题,你全都会吗?

现在面试中&#xff0c;算法出现的频率越来越高了&#xff0c;大厂基本必考 今天给大家带来20个常见的前端算法题&#xff0c;重要的地方已添加注释&#xff0c;如有不正确的地方&#xff0c;欢迎多多指正&#x1f495; 大厂面试题分享 面试题库 前后端面试题库 &#xff08;…

基于RDF本体模型和图数据库实现知识查询与推理

基于RDF本体模型和图数据库实现知识查询与推理 基于RDF本体模型和图数据库实现知识查询与推理一、案例本体模型解释二、数据构建与查询 Here’s the table of contents: 基于RDF本体模型和图数据库实现知识查询与推理 本文主要使用ONgDB图数据库和Neosemantics组件&#xff0c;…

运行时内存数据区之虚拟机栈——操作数栈

操作数栈 每一个独立的栈帧中除了包含局部变量表以外&#xff0c;还包含一个后进先出(Last-In-First-Out)的操作数栈&#xff0c;也可以称之为表达式栈(Expression Stack)。操作数栈&#xff0c;在方法执行过程中&#xff0c;根据字节码指令&#xff0c;往栈中写入数据或提取数…

《花雕学AI》06:抢先体验ChatGPT的九个国内镜像站之试用与综合评测

最近ChatGPT持续大火&#xff0c;大家们是不是在网上看到各种和ChatGPT有趣聊天的截图&#xff0c;奈何自己实力不够&#xff0c;被网络拒之门外&#xff0c;只能眼馋别人的东西。看别人在体验&#xff0c;看别人玩&#xff0c;肯定不如自己玩一把舒服的啊。 上一期&#xff0…

视图的使用

为什么引入视图&#xff08;Views&#xff09; 如果您读过其他类似的书&#xff0c;可能会看到这些书在介绍视图时列举了许多引入视图的原因。其中认为最重要的原因是维护数据的独立性。那么什么是数据的独立性呢&#xff1f; 早期信息系统的设计与开发多采用模块驱动方式&am…

如何使用Win10搭建我的世界Minecraft服务器

简单几步在windwos搭建我的世界服务器,并通过cpolar工具将本地服务暴露到公网连接 1. Java环境搭建 以windows10系统为例&#xff0c;配置java环境&#xff0c;搭建我的世界服务器,下载最新版java版本 Java Downloads | Oracle 选择exe文件&#xff0c;下载完成后双击安装包…

从Hive源码解读大数据开发为什么可以脱离SQL、Java、Scala

从Hive源码解读大数据开发为什么可以脱离SQL、Java、Scala 前言 【本文适合有一定计算机基础/半年工作经验的读者食用。立个Flg&#xff0c;愿天下不再有肤浅的SQL Boy】 谈到大数据开发&#xff0c;占据绝大多数人口的就是SQL Boy&#xff0c;不接受反驳&#xff0c;毕竟大…

开发者笑疯了! LLaMa惊天泄露引爆ChatGPT平替狂潮,开源LLM领域变天

来源: 新智源 微信号&#xff1a;AI-era Meta的LLaMA模型开源&#xff0c;让文本大模型迎来了Stable Diffustion时刻。谁都没想 谁能想到&#xff0c;一次意外的LLaMA泄漏&#xff0c;竟点燃了开源LLM领域最大的创新火花。 一系列表现出色的ChatGPT开源替代品——「羊驼家族」…

全网最详细,Jmeter性能测试-性能基础详解,接口关联与编写Java脚本(三)

目录&#xff1a;导读前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09;前言 接口关联 接口关联…

水塘抽样解决随机选择问题

1.简介 水塘抽样是一系列的随机算法&#xff0c;其目的在于从包含n个项目的集合S中选取k个样本&#xff0c;其中n为一很大或未知的数量&#xff0c;尤其适用于不能把所有n个项目都存放到内存的情况。最常见例子为Jeffrey Vitter在其论文中所提及的算法R。 2.算法步骤&#xff1…

机器学习算法系列(三)

机器学习算法之–对数几率回归&#xff08;逻辑斯蒂回归&#xff09;算法 上个算法&#xff08;算法系列二&#xff09;介绍了如何使用线性模型进行回归学习&#xff0c;但若要做的是分类任务&#xff0c;则需要找一个单调可微函数将分类任务的真实标记y与线性回归模型的预测值…

一次etcd变更引发的惨案

问题描述 在做etcd的数据变更时候&#xff0c;etcd在组成集群的时候出现leader不断切换问题&#xff0c;导致集群不稳定&#xff0c;都面将不健康的etcd节点踢出&#xff0c;只剩etcd单节点&#xff0c;后面将踢出的etcd节点重新加入现有etcd&#xff0c;导致etcd集群奔溃&…

【故障诊断】基于 KPCA 进行降维、故障检测和故障诊断研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…

快速搭建第一个SpringCloud程序

目录 1、Spring Boot项目脚手架快速搭建 1.1 生成工程基本配置 1.2 生成工程。 1.3 导入开发工具&#xff08;此处为Idea&#xff09; 1.4 运行代码 1.5 验证是否能访问 2、Spring Cloud环境搭建 2.1 版本匹配问题 2.2 Spring Cloud环境测试 3、引入Eureka Server 3…

运行时内存数据区之虚拟机栈——局部变量表

这篇内容十分重要,文字也很多,仔细阅读后,你必定有所收获! 基本内容 与程序计数器一样&#xff0c;Java虚拟机栈&#xff08;Java Virtual Machine Stack&#xff09;也是线程私有的&#xff0c;它的生命周期与线程相同。虚拟机栈描述的是Java方法执行的线程内存模型&#xf…

【从零开始学Skynet】基础篇(六):MySql数据库安装操作

游戏服务端的另一项重要功能是保存玩家数据&#xff0c;Skynet提供了操作MySQL数据库、MongoDB数据库的模块。1、数据库安装 首先安装Mysql服务器&#xff0c;打开终端输入如下指令&#xff1a; sudo apt-get install mysql-server 按下回车&#xff0c;输入密码后开始安装&a…

项目1实现login登录功能方案设计第三版

需求优化点:MySQL表常用功能模块实现方案index页面home页面需求 实现一个登录功能 实现的功能 注册(邮箱注册)登录(邮箱密码)重置密码查看操作记录(登录, 注册, 重置密码, 登出. 都算操作)登出在第2版的基础上进行优化:\ 优化点: VerificationCode(验证码储存库): 增加时间字段…

青藤首提“业安融合”理念,正式发布先进云安全方案CNAPP

4月18日&#xff0c;以“云时代&#xff0c;安全变了”为主题的2023年云安全高峰论坛在北京举行。会上&#xff0c;青藤首次提出“业安融合”理念&#xff0c;正式发布先进云安全方案CNAPP。 中国全面进入云和数字化时代 当前&#xff0c;全球已进入数字经济时代&#xff0c;…

前端自动化测试之葵花宝典

首先聊一下概念&#xff0c;Web 前端自动化测试是一种通过编写代码来自动化执行 Web 应用程序的测试任务的方法&#xff0c;它通常使用 JavaScript 和测试框架 (如 Selenium、Appium 等) 来实现。 Web 前端自动化测试的优点是可以提高测试效率、减少测试时间和测试成本&#x…