第十四届蓝桥杯_省赛B组(C).冶炼金属

题目如下:

在这里插入图片描述
拿到题我们来看一下,题目的意思,就是求出N个记录中的最大最小值,言外之意就是,如果超过了这个最大值不行,如果小于这个最小值也不行,所以我们得出,这道题是一个二分答案的题目,求出分界点。
首先我们输入 N 个组别,分别输入a , b 。
我们先讨论最小值,我们写一个binary_min函数,用来二分答案的最小值,记最小值为 ans
首先,左边界为 1 通过题目我们知道 我们要求的 V在分母上 所以我们最小为1,最大则为当前a(分子)的值
下来我们开始二分,在二分答案中我们应该写成while(l<r)这样我们就不用记录中间的状态了(下面注释中会说到), mid=l+r>>1取中值,下来进入主要逻辑,当a/mid(V)<=b的时候,我们可以得出我们现在的值在分界点的左边,需要将V的值变大,那么就需要将分母上的值(mid)变小,那么我们就需要向左收缩区间令r=mid(这里说明为什么应该为l<r,我们在之前的二分中,左闭右开时,循环的条件为while(l<=r),而这次需要写成l<r,我们最终要找的是临界点 所以我们最后需要 l==r 而不是l=r+1)
当写成while(l<=r)时,错误写法

// 错误示例:使用 l <= r 但不记录答案
int binary_min(int a, int b) {int l = 1, r = a;while (l <= r) {  // 问题1:循环会在 l=r+1 时结束int mid = (l + r) / 2;if (a / mid <= b) {r = mid - 1;  // 问题2:可能错过正确答案} else {l = mid + 1;}}return l;  // 错误:循环结束时 l 可能已超出有效范围
}

最主要的就是可能会直接跳过最佳的答案,导致答案不正确(采用左闭右闭的写法时,应该确保每次右边的边界都不会被跳过,由于我们的循环条件为l<r)所以我们应该记录一下右边界的值
所以应该向右收缩时记录值

		if (a / mid <= b) {ans = mid;  // 记录当前有效解r = mid - 1;  // 向左收缩(关键:r=mid-1而非r=mid)} else {l = mid + 1;}

正确写法

int binary_min(int a, int b) {int l = 1, r = a;while (l < r) {int mid = (l + r) >> 1;if (a / mid <= b) {r = mid;  // 保留当前 mid 作为候选} else {l = mid + 1;}}return l;  // 循环结束时 l 即为答案
}

了解了这一原理,下来继续写题,我们写完函数之后试着输出一下。
在这里插入图片描述
得到了这样一组数据,为什么会出现这种呢?因为有三个记录,每个记录对应着一个最小值,对于每个 (a, b),满足条件的 V 可能形成一个区间 [min_V, max_V]。当有多组输入时,我们需要找到一个公共的 V 范围,使得所有组的条件都被满足。
代码

	ans=max(ans,binary_min(a,b));ans2=min(ans2,binary_max(a,b));

我们每次都会获得一个V我们要在所有的可能最小值里面选出一个最大的,在所有可能得最大值中选择一个最小的,以此来满足公共区间例如在上面的例子中,18已经是最小的值了,所以我们答案可以大于等于18,所以我们需要取这一堆数的最大值,同理
在这里插入图片描述
获得了每组数据的最大上限,大的不一定全部满足,小的一定全部满足,找到其中的最小值,就是我们最终答案的最大值

AC代码:

#include <iostream>
#include<limits.h>
#include<algorithm>
using namespace std;
//找最大值
int binary_max(int a,int b){int l=1,r=a;while(l<r){int mid=(l+r+1)>>1;if((a/mid)>=b){l=mid;}elser=mid-1;}return l;
}//找最小值
int binary_min(int a,int b){int l=1,r=a;while(l<r){int mid=(l+r)>>1;if((a/mid)<=b){r=mid;}elsel=mid+1;}return l;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int N;cin>>N;int ans=INT_MIN,ans2=INT_MAX;while(N--){int a,b;cin>>a>>b;ans=max(ans,binary_min(a,b));ans2=min(ans2,binary_max(a,b));}cout<<ans<<" "<<ans2;return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

​​Android 如何查看CPU架构?2025年主流架构有哪些?​

在开发安卓应用或选购手机时&#xff0c;了解设备的CPU架构至关重要。不同的架构影响性能、兼容性和能效比。那么&#xff0c;​​如何查看安卓设备的CPU架构&#xff1f;2025年主流架构有哪些&#xff1f;不同架构之间有什么区别&#xff1f;​​ 本文将为你详细解答。 ​​1.…

飞算 JavaAI 2.0.0:开启老项目迭代维护新时代

在软件开发领域&#xff0c;老项目的迭代与维护一直是开发团队面临的难题。代码逻辑混乱、技术栈陈旧、开发效率低下等问题&#xff0c;让老项目改造犹如一场 “噩梦”。而飞算 JavaAI 2.0.0 版本的正式上线&#xff0c;通过三大核心能力升级&#xff0c;为老项目开发带来了全新…

Linux初步介绍

Linux是一种开源的类Unix操作系统内核&#xff0c;广泛应用于服务器、桌面、嵌入式设备等各种计算平台。它由Linus Torvalds于1991年首次开发&#xff0c;因其稳定性、安全性和灵活性&#xff0c;被全球开发者和企业广泛采用。 特点&#xff1a; 开放性&#xff08;开源&#…

OneNet + openssl + MQTT

1.OneNet 使用的教程 1.在网络上搜索onenet&#xff0c;注册并且登录账号。 2.产品服务-----物联网服务平台立即体验 3.在底下找到立即体验进去 4.产品开发------创建产品 5.关键是选择MQTT&#xff0c;其他的内容自己填写 6.这里产品以及开发完成&#xff0c;接下来就是添加设…

行为设计模式之Memento(备忘录)

行为设计模式之Memento&#xff08;备忘录&#xff09; 前言&#xff1a; 备忘录设计模式&#xff0c;有点像vmware快照可以回滚&#xff0c;idea的提交记录同样可以混滚&#xff0c;流程引擎中流程可以撤销到或者回滚到某个指定的状态。 1&#xff09;意图 在不破坏封装性的…

动画直播如何颠覆传统?解析足球篮球赛事的数据可视化革命

在5G和AI技术快速发展的今天&#xff0c;体育赛事直播正在经历一场深刻的变革。传统视频直播虽然能提供真实的比赛画面&#xff0c;但在战术可视化、数据深度和交互体验方面存在明显短板。而基于实时数据驱动的动画直播技术&#xff0c;正通过创新的方式弥补这些不足&#xff0…

二刷苍穹外卖 day01

nginx nginx反向代理 将前端发送的请求由nginx转发到后端服务器 好处&#xff1a; 提速&#xff1a;nginx本身可缓存数据 负载均衡&#xff1a;配置多台服务器&#xff0c;大量请求来临可均衡分配 保证后端安全&#xff1a;不暴露后端服务真实地址 server{listen 80;server_…

5.2 HarmonyOS NEXT应用性能诊断与优化:工具链、启动速度与功耗管理实战

HarmonyOS NEXT应用性能诊断与优化&#xff1a;工具链、启动速度与功耗管理实战 在HarmonyOS NEXT的全场景生态中&#xff0c;应用性能直接影响用户体验。通过专业的性能分析工具链、针对性的启动速度优化&#xff0c;以及精细化的功耗管理&#xff0c;开发者能够构建"秒…

模型训练-关于token【低概率token, 高熵token】

Qwen团队新发现&#xff1a;大模型推理能力的提高仅由少数高熵 Token 贡献 不要让低概率token主导了LLM的强化学习过程 一 低概率词元问题 论文&#xff1a;Do Not Let Low-Probability Tokens Over-Dominate in RL for LLMs 在RL训练过程中&#xff0c;低概率词元&#xff08…

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag

gRPC、WebSocket 与 HTTP 的核心区别对比

gRPC、WebSocket 与 HTTP 的核心区别对比&#xff0c;涵盖通信模式、协议特性及适用场景&#xff1a; &#x1f504; ‌一、通信模式‌ ‌HTTP‌ ‌单向请求-响应‌&#xff1a;客户端发起请求&#xff0c;服务器返回响应后连接立即关闭13。‌无状态协议‌&#xff1a;每次请求…

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…

讲讲JVM的垃圾回收机制

垃圾回收就是对内存堆中已经死亡或者长时间没有使用的对象进行清楚或回收。 JVM 在做 GC 之前&#xff0c;会先搞清楚什么是垃圾&#xff0c;什么不是垃圾&#xff0c;通常会通过可达性分析算法来判断对象是否存活。 在确定了那些垃圾可以被回收后&#xff0c;垃圾回收器&…

QT软件外包开发费用

国内QT软件外包开发费用是一个非常复杂的问题&#xff0c;没有一个固定的价格&#xff0c;它受到多种因素的影响。以下将详细阐述影响QT软件外包开发费用的主要因素&#xff0c;并提供大致的价格区间供参考&#xff08;请注意&#xff0c;这些价格仅为估算&#xff0c;实际报价…

iOS 16 SwiftUI 优雅跳转实践:用枚举路由和 NavigationStack 实现多页面导航

引言&#xff1a;跳转的混乱与优雅的必要性 SwiftUI 给我们带来了声明式界面的全新开发体验&#xff0c;但当涉及到页面跳转时&#xff0c;许多开发者仍然面临一些“旧痛”。最初的 NavigationLink(destination:isActive:) 或 sheet(isPresented:) 等方式虽然能用&#xff0c;…

TikTok矩阵养号实战:住宅IP纯净度与设备指纹联动方案

在TikTok矩阵运营中&#xff0c;住宅IP纯净度和设备指纹管理是规避风控的核心。以下方案整合多平台风控逻辑与实战数据&#xff0c;覆盖环境隔离、行为模拟到风险防控全流程。 &#x1f527; 一、住宅IP纯净度维持策略 IP筛选与验证 静态住宅IP优选&#xff1a;核心账号绑定目标…

Elasticsearch增删改查语句

创建索引库&#xff1a;不带映射的 PUT /索引名称 {"settings": {"number_of_shards": 3, // 主分片数"number_of_replicas": 1 // 每个主分片的副本数} } 创建带映射的索引库&#xff1a; PUT /products {"settings": {"…

树莓派4B, ubuntu20.04, 安装Ros Noetic[踩坑记录]

一、安装过程 1. 硬件要求 树莓派4B (建议4GB或8GB内存版本) 至少16GB的microSD卡 2. 下载并安装Ubuntu 20.04 Ubuntu 20.04 LTS (Focal Fossa) for Raspberry Pi 使用Raspberry Pi Imager或BalenaEtcher将镜像写入microSD卡 3. 安装ROS Noetic ​# 设置sources.list s…

视觉slam--框架

视觉里程计的框架 传感器 VO--front end VO的缺点 后端--back end 后端对什么数据进行优化 利用什么数据进行优化的 后端是怎么进行优化的 回环检测 建图 建图是指构建地图的过程。 构建的地图是点云地图还是什么信息的地图&#xff1f; 建图并没有一个固定的形式和算法…

每日算法 -【Swift 算法】删除链表的倒数第 N 个结点

🧩 Swift | 删除链表的倒数第 N 个结点(含详细注释) 在刷算法题时,我们经常会遇到关于链表的题目,而「删除链表的倒数第 N 个节点」是其中一个非常经典的题。今天我们就用 Swift 来实现它,并梳理清楚整个思路。 🧠 一、题目描述 给你一个链表,删除链表的倒数第 n 个…