当前位置：首页 > news >正文

算法日记33：14届蓝桥C++B冶炼金属（二分答案）

news 来源：原创 2025/8/29 8:53:42

一、题目：

在这里插入图片描述

二、题解：

1、思路解析：

1）首先我们可以发现题目的样例数量为（ $n <= 1000$ ），因此我们可以考虑 $O(n*log^n)$ 时间复杂度的算法

在这里插入图片描述

2）通过观察题目我们可以发现，要求我们求解答案的最小值与最大值，且答案拥有一定的单调性

3）因此我们的第一个思想是用二分答案求解：

2、二分答案详细过程：

1）找变量关系，判断合法区间

通过画图我们发现，当转化率 $V$ 不断增加时， $b [i]$ 的变化如下，虽然一整段 $b [i]$ 的值单调性，但是我们可以对其进行分段
- 二分： $a [i] / x <= b [i]$ 的区间，求解最小值（蓝色区间）
- 二分： $a [i] / x >= b [i]$ 的区间，求解最大值（红色区间）

2）判断区间端点

1^# 找最小值

二分函数构建
- 此时，我们发现其合法区间为 $<= b [i]$ （因为我们要使得我们想要求解的最值处于划分的区间边界)
- 因此我们可以通过判断 $a [i] / x$ 的值来判断是否合法(最后return r)

//合法区间<=b[i]的值
bool check_min(ll x) //x表示当前的转化率
{for(ll i=1;i<=n;i++) {if(a[i]/x>b[i]) return false;}return true;
}

二分入口构建
- 当check_min(mid)成立时，说明此时 $a [i] / x <= b [i]$ ， $mi d$ 偏大，因此r=mid
- 最后reutrn r即可(如图所示， $r$ 所指向的部分为答案)

  ll l = 1, r = 1e9 + 7;while(l+1<r)  //二分答案找最满足条件的最小值{ll mid=(l+r)>>1;if(check_min(mid))   r=mid; else l=mid;}v_min=r;

2^#找最大值

二分函数构建
- 此时，我们发现其合法区间为 $>= b [i]$ （因为我们要使得我们想要求解的最值处于划分的区间边界)
- 因此我们可以通过判断 $a [i] / x$ 的值来判断是否合法(最后return L)

bool check_max(ll x) //合法区间>=b[i]的值
{for(ll i=1;i<=n;i++) {if(a[i]/x<b[i]) return false;}return true;
}

二分入口构建
- 当check_min(mid)成立时，说明此时 $a [i] / x >= b [i]$ ， $mi d$ 偏小，因此l=mid
- 最后reutrn l即可(如图所示， $l$ 所指向的部分为答案)

 l=1,r=1e9+7;while(l+1<r)  //二分答案找满足条件的最大值{ll mid=(l+r)>>1;if(check_max(mid)) l=mid;else r=mid;}v_max=l;

3、完整代码解析：

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 2e5 + 7;
ll a[N], b[N], n;//合法区间<=b[i]的值
bool check_min(ll x) //x表示当前的转化率
{for(ll i=1;i<=n;i++) {if(a[i]/x>b[i]) return false;}return true;
}bool check_max(ll x) //合法区间>=b[i]的值
{for(ll i=1;i<=n;i++) {if(a[i]/x<b[i]) return false;}return true;
}int main() {cin >> n;ll v_min,v_max;for (int i = 1; i <= n; i++) {cin >> a[i] >> b[i];}//转化率V->:不断增加        Vmin       Vmax//结果:>b[i] >b[i]  >b[i] =b[i] =b[i] =b[i]  <b[i] <b[i] <b[i]ll l = 1, r = 1e9 + 7;while(l+1<r)  //二分答案找最满足条件的最小值{ll mid=(l+r)>>1;if(check_min(mid))   r=mid; else l=mid;}v_min=r;l=1,r=1e9+7;while(l+1<r)  //二分答案找满足条件的最大{ll mid=(l+r)>>1;if(check_max(mid)) l=mid;else r=mid;}v_max=l;cout << v_min << ' ' << v_max;return 0;
}

算法日记33：14届蓝桥C++B冶炼金属（二分答案）

一、题目： 二、题解： 1、思路解析： 1）首先我们可以发现题目的样例数量为（ n < 1000 n<1000 n<1000），因此我们可以考虑 O ( n ∗ l o g n ) O(n*log^n) O(n∗logn)时间复杂度的算法 …...

编程日记 2025/8/29 8:53:42

【YOLO V5】目标检测 WSL2 AutoDL VScode SSH

【YOLO V5】目标检测 WSL2 AutoDL VScode SSH 前言整体思路理解向YOLO 目标检测完整流程环境配置Anaconda 获取 YOLO 代码与预训练模型下载 YOLOv5 代码和预训练模型配置 YOLOV5 工程环境解压 YOLOv5 源代码并添加预训练模型调整依赖版本选择对应的 Python 解释器数据集准备…...

编程日记 2025/8/29 18:37:40

前端基础之ajax

vue-cli配置代理服务器解决跨域问题我们可以使用一个代理服务器8080，Vue项目8080发送请求向代理服务器8080发送请求，再由在理服务器转发给后端服务器首先需要在vue.config.js中配置代理服务器 const { defineConfig } require(vue/cli-service) modul…...

编程日记 2025/8/30 6:31:20

vscode离线配置远程服务器

目录一、前提二、方法 2.1 查看vscode的commit_id 2.2 下载linux服务器安装包 2.3 安装包上传到远程服务器，并进行文件解压缩三、常见错误 Failed to set up socket for dynamic port forward to remote port（vscode报错解决方法）-C…...

编程日记 2025/8/30 3:25:48

C语言——string.h下的特殊库函数

string.h下的特殊函数 strtok(分割字符串）strerror(错误码信息）memcpy(拷贝）memmove(拷贝）memset(设置内存）memcmp(比较大小） strtok(分割字符串） char * strtok ( char * str, const char * s…...

编程日记 2025/8/29 18:52:10

烟花燃放安全管控：智能分析网关V4烟火检测技术保障安全

一、方案背景在中国诸多传统节日的缤纷画卷中，烟花盛放、烧纸祭祀承载着人们的深厚情感。一方面，烟花璀璨，是对节日欢庆氛围的热烈烘托，寄托着大家对美好生活的向往与期许；另一方面，袅袅青烟、点点烛光&a…...

编程日记 2025/8/28 9:13:16

【一个月备战蓝桥算法】递归与递推

字典序在刷题和计算机科学领域，字典序（Lexicographical order）也称为词典序、字典顺序、字母序，是一种对序列元素进行排序的方式，它模仿了字典中单词的排序规则。下面从不同的数据类型来详细解释字典序： …...

编程日记 2025/8/26 2:38:47

二、Java-封装playwright UI自动化(根据官网执行步骤，首先封装BrowserFactory枚举类及BrowserManager)

前言查看playwright官网，api文档了解到，playwright的基本步骤： 1、实例化一个playwright 2、启动一个浏览器类型 3、打开一个页面所以，在封装时需要有一个浏览器工厂类，定义不同的浏览器类型，在配置文…...

编程日记 2025/8/27 13:00:10

java项目之基于ssm的在线视频网站开发（源码+文档）

项目简介基于ssm的在线视频网站开发实现了以下功能： 该系统的目标用户包括管理员，用户。管理员上传视频，管理视频，查看视频留言，回复视频留言，管理视频收藏信息，管理公告，管理用户…...

编程日记 2025/8/29 16:46:21

观察者模式的C++实现示例

核心思想观察者模式是一种行为型设计模式，定义了对象之间的一对多依赖关系。当一个对象（称为Subject，主题）的状态发生改变时，所有依赖于它的对象（称为Observer，观察者）都会自动收到…...

编程日记 2025/8/28 1:56:43

c语言中的主要知识点

一、基础语法与结构程序结构包含顺序结构、选择结构（if/switch）、循环结构（for/while/do-while）。程序必须包含且仅有一个main函数作为入口。数据类型与变量基本类型：整型（int、long）、浮…...

编程日记 2025/8/29 12:03:51

Pytorch构建LeNet进行MNIST识别 #自用

LeNet是一种经典的卷积神经网络（CNN）结构，由Yann LeCun等人在1998年提出，主要用于手写数字识别（如MNIST数据集）。作为最早的实用化卷积神经网络，LeNet为现代深度学习模型奠定了基础，…...

编程日记 2025/8/29 19:32:40

docker：Dockerfile案例之自定义centos7镜像

1 案例需求自定义centos7镜像。要求： 默认登录路径为 /usr可以使用vim 2 实施步骤编写dockerfile脚本 vim centos_dockerfile 内容如下： #定义父镜像 FROM centos:7#定义作者信息 MAINTAINER handsome <handsomehandsome.com># 设置阿里云…...

编程日记 2025/8/30 5:25:21

post get 给后端传参数

post 方式一 ： data: params 作为请求体（Request Body）传递： 你已经展示了这种方式，通过data字段直接传递一个对象或数组。这种方式通常用于传递复杂的数据结构。dowmfrom: function (params) { return request({ u…...

编程日记 2025/8/27 8:16:34

Linux 系统不同分类的操作命令区别

Linux 系统有多种发行版，每种发行版都有其独特的操作命令和工具。以下是一些常见的分类及其操作命令的区别： 1. 基于 Red Hat 的发行版 (RHEL, CentOS, Fedora) 1.1 包管理安装软件包： bash复制 sudo yum install <package> 更新软件包： bash复制 sudo yum update…...

编程日记 2025/8/28 9:29:07

Checkpoint 模型与Stable Diffusion XL（SDXL）模型的区别

Checkpoint 模型与 Stable Diffusion XL（SDXL）模型在功能、架构和应用场景上有显著区别，以下是主要差异的总结： 1. 基础架构与定位 Checkpoint 模型是基于 Stable Diffusion 官方基础模型（如 SD 1.4/1.5）…...

编程日记 2025/8/29 18:45:22

软件工程与实践（第4版新形态）练习与实践1

软件工程与实践（第4版新形态） 练习与实践1 1.填空题 (1)程序，文档 (2)系统软件，支撑软件，应用软件 (3)系统方法 (4)软件开发和维护 (5)工程的概念、原理、技术和方法 (6)实现软件的优质高产 (7)软件开发技术和…...

编程日记 2025/8/28 16:44:05

探秘基带算法：从原理到5G时代的通信变革【九】QPSK调制/解调

文章目录 2.8 QPSK 调制 / 解调简介QPSK 发射机的实现与原理QPSK 接收机的实现与原理QPSK 性能仿真QPSK 变体分析本博客为系列博客，主要讲解各基带算法的原理与应用，包括：viterbi解码、Turbo编解码、Polar编解码、CORDIC算法、CRC校验、FFT/…...

编程日记 2025/8/30 0:43:58

侯捷 C++ 课程学习笔记：深入理解智能指针

文章目录每日一句正能量一、引言二、智能指针的核心概念（一）std::unique_ptr（二）std::shared_ptr（三）std::weak_ptr 三、学习心得四、实际应用案例五、总结每日一句正能量如果说幸福是一个悖论&#xff…...

编程日记 2025/8/30 3:42:01

基于Qwen-VL的手机智能体开发

先上Demo： vl_agent_demo 代码如下： 0 设置工作目录： 你的工作目录需要如下： 其中utils文件夹和qwenvl_agent.py均参考自 GitHub - QwenLM/Qwen2.5-VL: Qwen2.5-VL is the multimodal large language model series developed by …...

编程日记 2025/8/29 12:09:35

系统盘还原成正常U盘

选择格式化,等格式化完毕就完了点击还原设备的默认值格式化就完了...

编程日记 2025/8/16 12:10:49

Leetcode 103: 二叉树的锯齿形层序遍历

Leetcode 103: 二叉树的锯齿形层序遍历问题描述： 给定一个二叉树，返回其节点值的锯齿形层序遍历（即第一层从左到右，第二层从右到左，第三层从左到右，依此类推）。适合面试的解法：广…...

编程日记 2025/8/29 11:29:50

FastGPT 引申：基于 Python 版本实现 Java 版本 RRF

文章目录 FastGPT 引申：基于 Python 版本实现 Java 版本 RRF函数定义使用示例 FastGPT 引申：基于 Python 版本实现 Java 版本 RRF 函数定义使用 Java 实现 RRF 相关的两个函数：合并结果、过滤结果 import java.util.*;// 搜索结果类型定义…...

编程日记 2025/8/29 21:32:24

C++中的无锁编程

引言在当今多核处理器普及的时代，并发编程已成为高性能应用程序开发的关键技术。传统的基于锁的同步机制虽然使用简单，但往往会带来性能瓶颈和死锁风险。无锁编程（Lock-Free Programming）作为一种先进的并发编程范式&#xff0c…...

编程日记 2025/8/28 7:45:17

【全栈开发】---- 一文掌握 Websocket 原理，并用 Django 框架实现

目录介绍底层原理握手环节详解： 收发数据（加密） Django 中配置 channels 1、注册 channels 2、在 settings.py 中添加 asgi_application 3、修改 asgi.py 文件 4、routing 5、consumers 实现聊天室介绍 WebSocket是一种先进的通信协议&…...

编程日记 2025/8/28 14:04:36

游戏引擎学习第135天

仓库:https://gitee.com/mrxiao_com/2d_game_3 回顾 game_asset.cpp 的创建在开发过程中，不使用任何现成的游戏引擎或第三方库，而是直接基于 Windows 进行开发，因为 Windows 目前仍然是游戏的标准平台，因此首先在这个环境中进行…...

编程日记 2025/8/16 12:03:39

国内支持Stable Diffusion模型的平台

国内支持Stable Diffusion模型的平台截至2025年3月，国内支持SD模型的平台主要包括以下六类，覆盖不同用户需求和技术层级： 一、模型分享与下载平台 Liblib.ai 描述：国内最大SD原创模型社区，提供海量基础模型、Lora…...

编程日记 2025/8/29 15:09:46

扣子（Coze）：重构AI时代的工作流革命

文章目录扣子（Coze）：重构AI时代的工作流革命使用Coze：一、工作流的本质：从单点智能到系统智能二、扣子工作流的技术基因三、场景化实践：从知识库到智能员工四、未来图景：AI Agent的进化之路结语…...

编程日记 2025/8/28 19:09:44

alloc、malloc 与 allocator：内存管理三剑客

内存管理是C语言开发者的核心能力，也是系统级编程的基石。一、内存分配三剑客：malloc/calloc/realloc 1. malloc函数原理 int* arr (int*)malloc(5 * sizeof(int)); // 分配20字节空间（假设int为4字节） 从堆区分配指定字节的连…...

编程日记 2025/8/29 3:45:04

单细胞分析（21）——SCENIC 分析流程（singularity容器版）

SCENIC 分析流程笔记 SCENIC (Single-Cell rEgulatory Network Inference and Clustering) 是一种基于单细胞 RNA 测序数据的调控网络分析方法，主要用于识别调控因子（TFs）及其靶基因（Regulons），并评估这些…...

编程日记 2025/8/29 6:49:38

亚马逊云科技Marketplace（中国区）上架专业服务产品， “云生态连接器”价值凸显

近日，由西云数据运营的亚马逊云科技Marketplace（中国区）正式支持专业服务产品。此次发布将大幅简化企业对云专业服务的采购流程，实现云软件从规划、部署到支持的全生命周期管理，同时也为合作伙伴提供了更多的销售机会。…...

编程日记 2025/8/30 3:25:07

拉普拉斯·隆格·楞次矢量

L − R − L L-R-L L−R−L 矢量的推导有平方反比有心力： F ⃗ − k r 2 r ^ \vec F-\dfrac{k}{r^2}\hat r F −r2kr^ 显然角动量 L ⃗ r ⃗ p ⃗ \vec L\vec r\times \vec p L r p 守恒。故 ∣ L ⃗ ∣ Const \begin{vmatrix}\vec L\end{vmatrix}\…...

编程日记 2025/8/29 13:59:29

GStreamer —— 2.3、Windows下Qt加载GStreamer库后运行 - “教程3:动态管道“（附：完整源码）

运行效果（音频） 简介上一个教程演示了GStreamer 概念。本教程中的管在它设置为 playing 状态之前完全构建。这没关系。如果我们没有采取进一步的行动，数据会到达 pipeline 的 pipeline 和 pipeline 将生成错误消息并停止。但我们将采取进一…...

编程日记 2025/8/27 2:38:24

jupyter notebook更改文件存储路径

默认情况打开是这样的进入cmd或者Anaconda Prompt，输入以下命令 jupyter notebook --generate-config进入该目录打开该文件，CTRLF 查找c.ServerApp.root_dir 进行修改。这样就修改好啦！...

编程日记 2025/8/25 13:21:21

基于遗传算法的无人机三维路径规划仿真步骤详解

基于遗传算法的无人机三维路径规划仿真步骤详解一、问题定义目标：在三维空间内，寻找从起点到终点的最优路径，需满足：避障：避开所有障碍物。路径最短：总飞行距离尽可能短。平滑性：转折角度不宜过大，降低机动能耗。输入：三维地图（含障碍物，如立方体、圆柱体）。起…...

编程日记 2025/8/28 20:29:35

①EtherCAT转Modbus485RTU网关多路同步高速采集无需编程串口服务器

EtherCAT转Modbus485RTU网关多路同步高速采集无需编程串口服务器https://item.taobao.com/item.htm?ftt&id798036415719 型号 1路总线EC网关 MS-A2-1011 2路总线EC网关 MS-A2-1021 4路总线EC网关 MS-A2-1041 EtherCAT 串口网关 EtherCAT 转 RS485 技术规格 …...

编程日记 2025/8/28 1:40:06

Spring Boot WebFlux 中 WebSocket 生命周期解析

Spring Boot WebFlux 中的 WebSocket 提供了一种高效、异步的方式来处理客户端与服务器之间的双向通信。WebSocket 连接的生命周期包括连接建立、消息传输、连接关闭以及资源清理等过程。此外，为了确保 WebSocket 连接的稳定性和可靠性，我们可以加入重试…...

编程日记 2025/8/29 1:16:41

集合论之集合的表示法

目录 1. 说明 2. 常用表示法 2.1 枚举法(Roster Notation) 2.2 构建法(Set-builder notation) 3. 其它表示法 1. 说明要表示一个集合，可以直接列出其元素，或者提供一种可以唯一地刻画其元素的方当。 2. 常用表示法 2.1 枚举法(Roster Notatio…...

编程日记 2025/8/30 7:28:33

【C语言】值传递与指针传递，以及 `.` 和 `-＞` 操作详解

在 C 语言中，函数参数的传递机制和结构体成员的访问方式是编程中的核心概念。值传递（pass-by-value）和指针传递（pass-by-pointer）决定了函数如何处理传入的数据，而 . 操作符和 -> 操作符则是访问结构体成员的两种主要工具。这两者密切相关，尤其在处理结构体时，它们…...

编程日记 2025/8/29 17:58:36

机器人训练环境isaac gym以及legged_gym项目的配置问题

完整的安装环境教程（强烈推荐）：...

编程日记 2025/8/29 5:35:21

DeepSeek 开源周回顾「GitHub 热点速览」

上周，DeepSeek 发布的开源项目用一个词形容就是：榨干性能！由于篇幅有限，这里仅列出项目名称和简介，感兴趣的同学可以前往 DeepSeek 的开源组织页面，深入探索每个项目的精彩之处！ 第一天 FlashML…...

编程日记 2025/8/28 18:16:57

冯 • 诺依曼体系结构

文章目录冯 • 诺依曼体系结构的介绍冯 • 诺依曼体系结构的由来内存是如何提高冯•诺依曼体系结构效率的？为什么程序运行之前必须先加载到内存？从软件层面上再理解冯 • 诺依曼体系结构（QQ聊天的数据流动）一些知识的补充冯 • …...

编程日记 2025/8/30 5:19:22

软考架构师笔记-存储管理

1.5 存储管理存储管理页式存储组织虚地址页号 | 页内地址页表页号 | 块号物理地址块号 | 页内地址访存两次：访问页表得到物理地址，根据物理地址得到数据就是把用户程序的空间分成若干页，把内存空间分成若干块，块和页的…...

编程日记 2025/8/29 23:53:14

【杂谈】信创电脑华为w515（统信系统）登录锁定及忘记密码处理

华为w515麒麟芯片版，还有非麒麟芯片版本，是一款信创电脑，一般安装的UOS系统。准备一个空U盘，先下载镜像文件及启动盘制作工具，连接如下： 百度网盘请输入提取码 http://livecd.uostools.com/img/apps/l…...

编程日记 2025/8/29 9:52:52

C#实现语音合成播报器——基于System.Speech的语音交互方案，在windows上实现语音播报指定文本

——基于System.Speech的语音交互方案，在windows上实现语音播报指定文本一、语音合成播报应用场景语音合成播报器广泛应用于以下领域： 工业控制：生产线异常报警、设备状态实时播报（如网页4中的WinCC语音报警插件）…...

编程日记 2025/8/29 20:58:16

【数据库】关系代数

关系代数一、关系代数的概念二、关系代数的运算2.1 并、差、交2.2 投影、选择2.3 笛卡尔积2.4 连接2.5 重命名2.6 优先级一、关系代数的概念关系代数是一种抽象的数据查询语言用对关系的运算来表达查询运算对象：关系运算符：4类运算结果：…...

编程日记 2025/8/28 18:07:37

点云滤波方法：特点、作用及使用场景

点云滤波是点云数据预处理的重要步骤，目的是去除噪声点、离群点等异常数据，平滑点云或提取特定频段特征，为后续的特征提取、配准、曲面重建、可视化等高阶应用打下良好基础。以下是点云中几种常见滤波方法的特点、作用及使用场景：…...

编程日记 2025/8/29 8:57:33

MWC 2025 | 移远通信大模型解决方案加速落地，引领服务机器人创新变革

随着人工智能、大模型等技术的蓬勃发展，生成式AI应用全面爆发。在此背景下，服务机器人作为大模型技术在端侧落地的关键场景，迎来了前所未有的发展机遇。作为与用户直接交互的智能设备，服务机器人需要应对复杂场景下的感知、决策和…...

编程日记 2025/8/28 19:23:39

如何下载安装 PyCharm?

李升伟整理一、下载 PyCharm 访问官网打开 PyCharm 官网，点击 "Download" 按钮25。版本选择： 社区版（Community）：免费使用，适合个人学习和基础开发。专业版（Professional&#…...

编程日记 2025/8/28 10:01:49

STM32F407IGT的USB功能

使用STM32F407IGT的USB功能时，需注意硬件设计、协议配置、软件开发和调试等关键点。以下是分步指南和注意事项： 1. 硬件设计 USB接口选择： OTG FS（全速，12 Mbps）：内置PHY，适用于简单应用（如HID、CDC）。OTG HS（高速，480 Mbps）：需外接ULPI PHY芯片（如USB3300），…...

编程日记 2025/8/21 5:44:40