题解:T480718 eating
eating
题目背景
从前有个荣光的王国,小 A 是里面的国王,今天他要赐予他的子民以仓廪。
题目描述
在一条街上有 n n n 个饭店。小 A 站在这条街的最左端。
第 i i i 个饭店离这条街最左端的距离是 a i a_i ai,它所售卖的菜品的美味值是 b i b_i bi。
小 A 不想走太多路,但是又想吃到好吃的东西。因此他定义一个饭店的吸引力是 w i = b i a i w_i = \frac{b_i}{a_i} wi=aibi。
小 A 想知道吸引力最大的饭店的编号是多少。如果有多个吸引力最大的饭店,你要告诉他距离街道左端距离最近的那个饭店的编号。
输入格式
第一行是一个整数 n n n,表示商店的个数。
接下来 n n n 行,每行两个整数,表示一个商店离街道左端的距离 a i a_i ai 个菜品美味值 b i b_i bi。
输出格式
输出一行一个整数,表示答案。
样例 #1
样例输入 #1
3
1 2
2 4
3 9
样例输出 #1
3
样例 #2
样例输入 #2
3
1 2
2 3
3 4
样例输出 #2
1
样例 #3
样例输入 #3
3
1 1
2 3
4 6
样例输出 #3
2
提示
数据规模与约定
- 对 20 % 20\% 20% 的数据, n = 2 n = 2 n=2。
- 对 40 % 40\% 40% 的数据,保证 b i b_i bi 是 a i a_i ai 的倍数。
- 对 60 % 60\% 60% 的数据,保证给出的 a i a_i ai 单调递增。
- 对 80 % 80\% 80% 的数据,保证 n ≤ 1000 n \leq 1000 n≤1000。
- 对 100 % 100\% 100% 的数据,保证 2 ≤ n ≤ 1 0 5 2 \leq n \leq 10^5 2≤n≤105, 1 ≤ a i , b i ≤ 1 0 9 1 \leq a_i, b_i \leq 10^9 1≤ai,bi≤109, a i a_i ai 互不相同。
为了解决这个问题,我们可以遍历所有的饭店,计算每个饭店的吸引力 w i = b i a i w_i = \frac{b_i}{a_i} wi=aibi,并记录当前最大的吸引力和对应的饭店编号。如果有多个饭店的吸引力相同且都是最大的,我们还需要记录这些饭店中距离街道左端最近的饭店编号。
以下是具体的Python代码实现:
n = int(input().strip()) # 读取饭店数量
max_attraction = float('-inf') # 初始化最大吸引力为负无穷
closest_restaurant = 0 # 初始化距离街道左端最近的饭店编号为0(实际上这个初始值不会被使用)
answer = 0 # 初始化答案为0(实际答案会在这个基础上更新)for i in range(n):a_i, b_i = map(int, input().strip().split()) # 读取每个饭店的距离和美味值w_i = b_i / a_i # 计算吸引力# 如果当前饭店的吸引力大于已知的最大吸引力if w_i > max_attraction:max_attraction = w_i # 更新最大吸引力answer = i + 1 # 更新答案为当前饭店的编号# 如果当前饭店的吸引力等于已知的最大吸引力,但距离更近elif w_i == max_attraction and a_i < min(a_i for _, a_i in enumerate(range(answer-1, -1, -1))):# 注意这里我们假设answer-1之前的饭店的a_i都已经被读取过了,但实际上我们需要一个额外的数据结构来存储这些值# 但由于题目保证a_i互不相同,我们可以直接更新answer,因为更近的饭店一定在更前面被读取answer = i + 1 # 更新答案为当前饭店的编号print(answer) # 输出答案
然而,上面的代码在处理距离更近的饭店时存在逻辑上的不严谨,因为我们在遍历过程中并没有存储之前所有饭店的距离。但由于题目保证 a i a_i ai 互不相同,我们可以简化处理:当遇到吸引力相同的饭店时,我们直接更新答案,因为后读取的饭店(即距离更近的)会覆盖之前的答案。
下面是简化后的代码:
n = int(input().strip())
max_attraction = float('-inf')
answer = 0for i in range(n):a_i, b_i = map(int, input().strip().split())w_i = b_i / a_iif w_i > max_attraction or (w_i == max_attraction and i + 1 < answer):max_attraction = w_ianswer = i + 1print(answer)
这样,我们就可以正确地找到吸引力最大且距离街道左端最近的饭店编号了。
相关文章:
题解:T480718 eating
eating 题目背景 从前有个荣光的王国,小 A 是里面的国王,今天他要赐予他的子民以仓廪。 题目描述 在一条街上有 n n n 个饭店。小 A 站在这条街的最左端。 第 i i i 个饭店离这条街最左端的距离是 a i a_i ai,它所售卖的菜品的美味…...
MATLAB中matfile用法
目录 语法 说明 示例 创建 MAT 文件对象 启用对 MAT 文件的写访问权限 加载整个变量 将整个变量保存至现有 MAT 文件 加载和保存部分变量 确定变量大小 参数说明 局限性 提示 matfile的功能是访问和更改 MAT 文件中的变量,而不必将文件加载到内存中。 …...

Spring之Spring Bean的生命周期
Spring Bean的生命周期 通过BeanDefinition获取bean的定义信息调用构造函数实例化beanBean的依赖注入处理Aware接口(BeanNameAware、BeanFactoryAware、ApplicationContextAware)Bean的后置处理器BeanPostProcessor-前置初始化方法(Initiali…...

OSINT 开源情报中的地理定位方法
了解 OSINT 中的地理定位技术、如何获取地理位置数据以及如何将地理定位用于各种调查场景。 OSINT 中的地理定位基础知识 OSINT 代表开源情报,指的是从免费公共来源合法收集的有关个人或组织的信息。这包括在互联网上以及书籍、公共图书馆报告、报纸文章、新闻稿、…...
Java面试题系列 - 第17天
Java中的代理模式与动态代理 背景说明:代理模式是一种结构型设计模式,用于在客户端和目标对象之间提供一个代理或占位符。在Java中,动态代理技术允许在运行时创建代理对象,这在AOP(面向切面编程)和RPC&…...

开发环境搭建
1、Ubuntu 系统设置 root 用户密码 新安装的ubuntu没有设置 root 用户密码,打开终端,输入 sudo passwd root 执行命令后依次输入密码 2、虚拟机设置网络适配器 3、Ubuntu 系统下搭建 FTP 服务器 sudo apt-get update sudo apt-get install vsftpd sudo apt-get install vim…...
【NLP】关于参数do_sample的解释
在自然语言处理(NLP)领域,特别是在使用神经网络模型进行文本生成时,do_sample是一个常见的参数,用于控制模型生成文本的方式。具体来说,do_sample参数决定模型是否采用随机采样(sampling&#x…...
Vbox虚拟机+Ubuntu motest测试drm
1. 效果演示 大家做学习drm的时候,没有硬件测试平台不方便测试,这里给大家演示下如何基于Vbox虚拟机Ubuntu测试drm的一些功能,先看下演示视频。 没有光标测试: demo_vwmfgx_test_drm 带有光标测试: demo_vwmfgx_drm_with_cursor 可以看到,有…...
ArcGIS Pro SDK (九)几何 15 转换
ArcGIS Pro SDK (九)几何 15 转换 文章目录 ArcGIS Pro SDK (九)几何 15 转换1 创建地理转换2 创建复合地理变换3 创建投影转换4 创建高压基准变换5 创建复合高压基准变换6 决定转换7 地图点 - 地理坐标字符串转换 环境࿱…...

Spring IOC DI --- 认识IOC DI
T04BF 👋专栏: 算法|JAVA|MySQL|C语言 🫵 今天你敲代码了吗 文章目录 认识Ioc & DIIoc是什么?DI是什么? 认识Ioc & DI 我们知道,Spring 是一个开源框架,让我们的开发更加简单.但是更加具体来说,实际上Spring 是包含了众多工具方法的Ioc容器 …...
常用的python程序汇总——入门级
只用于记录最近的一些日常程序。 目录 前言 一、文件和目录管理 1.读取文件结构 读取所有文件夹和文件 读取到N级子文件夹和文件 只读取到N级子文件夹 2.遍历文件并处理(复制、删除) 说明: 二、数据分析和处理 三、数据可视化 四、…...

被问到MQ消息已丢失,该如何处理?
在分布式系统中,消息中间件(如 RabbitMQ、RocketMQ、Kafka、Pulsar 等)扮演着关键角色,用于解耦生产者和消费者,并确保数据传输的可靠性和顺序性。尽管我们通常会采取多种措施来防止消息丢失,如消息持久化、…...
open3d:ransac分割多个平面(源码)
1、背景介绍 随机采样一致性算法(RANSAC Random Sample Consensus)是一种迭代的参数估计算法,主要用于从包含大量噪声数据的样本中估计模型参数。其核心思想是通过随机采样和模型验证来找到数据中最符合模型假设的点。因此,只要事先给定要提取的参数模型,即可从点云中分割…...

Github 2024-07-17 开源项目日报 Top10
根据Github Trendings的统计,今日(2024-07-17统计)共有10个项目上榜。根据开发语言中项目的数量,汇总情况如下: 开发语言项目数量非开发语言项目3Python项目3Rust项目2TypeScript项目2MDX项目1项目化学习 创建周期:2538 天协议类型:MIT LicenseStar数量:161973 个Fork数量…...
vue3中Composition API写法 <script setup>标签中哪些可以不用导入即可使用?
在 Vue 3 中使用 <script setup> 时,确实有一些全局的 API 和宏可以直接使用,而不需要显式地从 vue 包中导入它们。这是因为 <script setup> 是专门为了提供更简洁的组件编写方式而设计的,它内部利用了编译时的语法糖。 以下是在…...

Facebook Dating:社交平台的约会新体验
随着社交媒体的普及和技术的发展,传统的社交方式正在经历革新,尤其是在约会这个领域。Facebook作为全球领先的社交平台,推出了Facebook Dating,旨在为用户提供一个全新的约会体验。本文将探讨Facebook Dating如何重新定义社交平台…...
【系统架构设计 每日一问】五 搜索型业务,采用MySQL+ES,如何保证数据一致性
将数据从MySQL同步到Elasticsearch(ES)中并保证一致性是一个常见的需求,特别是在需要快速全文搜索和分析功能的应用中。以下是一些常见的方法和实践来确保数据一致性: 1. 使用双写策略 描述:在应用程序层面ÿ…...

缓存穿透,缓存击穿,缓存雪崩
目录 介绍 缓存穿透 缓存击穿 缓存雪崩 原因 影响 解决方案 缓存穿透 防止缓存穿透->空值缓存案例 缓存击穿 使用互斥锁解决缓存击穿 介绍 缓存穿透 定义:缓存穿透是指用户查询数据,缓存和数据库中都不存在该数据(一般是发起恶意…...
运维 | 清理 Linux 磁盘空间方法汇总
清理 Linux 磁盘空间方法汇总 前言 系统磁盘不够用或占满了,导致部分应用或程序无法正常使用。 本章节将记录一些常用或常见的方法清理系统磁盘(持续更新中)。 常见操作 查看磁盘使用情况 cd / df -Th查找大文件和目录(根目…...

googleTest 源码主线框架性分析——TDD 01
TDD,测试驱动开发,英文全称Test-Driven Development,简称TDD,是一种不同于传统软件开发流程的新型的开发方法。它要求在编写某个功能的代码之前先编写测试代码,然后只编写使测试通过的功能代码,通过测试来推…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...

mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...

Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

c++第七天 继承与派生2
这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分:派生类构造函数与析构函数 当创建一个派生类对象时,基类成员是如何初始化的? 1.当派生类对象创建的时候,基类成员的初始化顺序 …...