二分算法模版
二分算法模版
- 实数二分算法模版
- 实数二分模版题
- 整数二分算法模版
- 向上取整二分模版
- 向下取整二分模版
- 二分模版的注意点
- 二分模版中check函数的实现
- 能够使用二分的条件
二分主要分两类,
一类是对实数进行二分,一类是对整数进行二分
对整数二分又分成2种,一种是向上取整的二分模版,一种是向下取整的二分模版
实数二分算法模版
//这里区间范围为
double l = 0 ,r = n;// 这里循环条件根据题意来,保留几位小数//如果题目要求保留6位小数,保险一点,再加2位,//循环条件就是保留8位小数 --->(r - l)while(r - l > 1e-8) //r - l {double mid = (r + l) / 2;if(check(mid))r = mid; //范围大了,缩小范围else l = mid; //范围小了扩大范围}
注意:浮点数二分相当于连续的,要加或者减一个很小的数, +1, -1 误差很大,所以都后面执行语句直接等于mid
区别于实数二分
实数二分模版题

#include<iostream>
#include<cstdio>using namespace std;int main()
{double x;scanf("%lf", &x);double l = -10000 ,r = 10000;while(r - l > 1e-8) //r - l 大于8位小数 (题目要求六位,这里取八位,保险一点){double mid = (r + l) / 2;if(mid * mid * mid >= x)r = mid; //范围大了,缩小范围else l = mid; //范围小了扩大范围}printf("%.6lf", l);return 0;
}
整数二分算法模版
向上取整二分模版
一般,可用来求最小值中的最大值或者最大值
// 每次注意找出二分的范围
//向上取整的区间为 [l, mid - 1] [mid, r]int l = 0, r = n;
while(l < r)
{int mid = l + r + 1 >> 1;if(check(mid)) //mid数据合法,扩大范围,看看有没有更大的l = mid; else //mid数据不合法,缩小范围r = mid - 1
}//结束循环的条件 l == r
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时,其更新操作是r = mid - 1或者l = mid;,此时为了防止死循环,计算mid时需要加1。
向下取整二分模版
一般,可用来求最大值中的最小值或者最小值
//向下取整的区间范围
//[l, mid] [mid + 1, r]int l = 0, r = n;
while(l < r)
{int mid = l + r >> 1;if(check(mid)) //mid数据合法 缩小区间看看有没有更小的r = mid;else //mid数据不合法,扩大区间 l = mid + 1;
}
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时,其更新操作是r = mid或者l = mid + 1;,计算mid时不需要加1
二分模版的注意点
二分模版有很多,选择自己适合的背就行
这个整数二分的注意点
1.循环条件都是 while(l < r) 都没有取等
2.向上取整的算法模版中 mid 还有多加1, 不加1的话会陷入死循环
3.二分使用的时候,是对一个有序的区间进行二分,如果这个区间无序,要对这个区间=进行排序
二分模版中check函数的实现
.check()函数的实现
check()函数,是二分模版中,最难的一部分。
作用就是判断二分的数据是否合法,满足题意
或者是找具有二段性的临界的判断条件
不同题的check函数都是不一样的,这只有靠自己做题,多积累,多体会和总结
能够使用二分的条件
能够使用二分解决问题,一般是具有单调性或者是二分性,或者是求一个区间的最大值或者最小值等
相关文章:
二分算法模版
二分算法模版 实数二分算法模版实数二分模版题 整数二分算法模版向上取整二分模版向下取整二分模版二分模版的注意点二分模版中check函数的实现能够使用二分的条件 二分主要分两类, 一类是对实数进行二分,一类是对整数进行二分 对整数二分又分成2种&…...
【CSS】字体效果展示
测试时使用了Google浏览器。 1.Courier New 2.monospace 3.Franklin Gothic Medium 4.Arial Narrow 5.Arial 6.sans-serif 7.Gill Sans MT 8.Calibri 9.Trebuchet MS 10.Lucida Sans 11.Lucida Grande 12.Lucida Sans Unicode 13.Geneva 14.Verdana 15.Segoe UI 16.Tahoma 17.…...
asp.net宠物流浪救助系统
asp.net宠物流浪救助系统 当领养人是无或者未领养的时候,就会显示领养申请按钮,登陆的用户可以申请领域该宠物,未登录会提示登陆然后转到登陆页面 宠物领养页面支持关键字查询符合条件的宠物 当有领养人时就隐藏领养申请按钮 社区交流意见…...
git常见命令
1、常用命令记录 1)切换分支 git checkout 分支名2)查看分支 查看远程分支 git branch -r 查看所有分支包括本地分支和远程分支 git branch -a3)合并分支 git merge 来源分支4)删除分支 删除本地分支:git branch …...
主成分分析(PCA)Python
实际问题研究中,常常遇到多变量问题,变量越多,问题往往越复杂,且各个变量之间往往有联系。于是,我们想到能不能用较少的新变量代替原本较多的旧变量,且使这些较少的新变量尽可能多地保留原来变量所反映的信…...
Leetcode—144. 二叉树的前序遍历【简单】
2023每日刷题(九十六) Leetcode—144. 二叉树的前序遍历 实现代码 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr…...
混淆矩阵、准确率、查准率、查全率、DSC、IoU、敏感度的计算
1.背景介绍 在训练的模型的时候,需要评价模型的好坏,就涉及到混淆矩阵、准确率、查准率、查全率、DSC、IoU、敏感度的计算。 2、混淆矩阵的概念 所谓的混淆矩阵如下表所示: TP:真正类,真的正例被预测为正例 FN:假负类…...
ChatGPT目前的AI一哥
ChatGPT和文心一言是两个不同的AI助手,各自有其独特的特点和应用场景。以下是对它们在智能回复、语言准确性和知识库丰富度等方面的简要比较: 智能回复:ChatGPT是由OpenAI开发的语言模型,具有强大的自然语言处理和生成能力&#x…...
认识思维之熵
经常有读者问我,说: 为什么向您请教一个问题,您总能很快指出在哪篇文章里面提到过,是因为您的记忆力特别好吗? 其实不是的。更重要的原因是:如果你经过系统训练,有意识地去获取知识的话&#x…...
蓝桥杯备战——1.点亮LED灯
1.解析原理图 由上图可以看到8个共阳LED灯接到了573输出口,而573输入接到单片机P0口上。当573 LE脚输入高电平时,输出随输入变化,当LE为低电平时,输出锁存。 由上图可以看到Y4C接到了或非门74HC02的输出端,而输入端为…...
【网络协议测试】畸形数据包——圣诞树攻击(DOS攻击)
简介 TCP所有标志位被设置为1的数据包被称为圣诞树数据包(XMas Tree packet),之所以叫这个名是因为这些标志位就像圣诞树上灯一样全部被点亮。 标志位介绍 TCP报文格式: 控制标志(Control Bits)共6个bi…...
Java基础面试题-5day
泛型 什么是泛型?有什么用? 泛型是jdk5引入的新特性,通过泛型可以提高代码的可读性和稳定性;当我们使用泛型时,传入的对象类型必须是指定的泛型类型,否则就会报错 泛型的使用方式有哪些? 一…...
软通智慧启动鲲鹏原生应用开发合作
1月25日,软通智慧科技有限公司启动鲲鹏原生应用开发合作,将基于鲲鹏硬件底座、openEuler、开发套件Kunpeng DevKit和应用使能套件Kunpeng BoostKit开展面向智慧园区、政务、水利水务等行业场景的软硬件原生应用开发,并持续发布性能更优的鲲鹏…...
【STM32】STM32F4中USB的CDC虚拟串口(VCP)使用方法
文章目录 一、前言二、STM32CubeMX生成代码2.1 选择芯片2.2 配置相关模式2.3 设置时钟频率2.4 生成代码2.5 编译并下载代码2.6 结果2.7 问题 三、回环测试3.1 打开工程3.2 添加回环代码3.3 编译烧录并测试 四、出现问题和解决方法4.1 烧录总是要自己插拔USB4.2 自己生成的工程没…...
网络协议与攻击模拟_06攻击模拟SYN Flood
一、SYN Flood原理 在TCP三次握手过程中, 客户端发送一个SYN包给服务器服务端接收到SYN包后,会回复SYNACK包给客户端,然后等待客户端回复ACK包。但此时客户端并不会回复ACK包,所以服务端就只能一直等待直到超时。服务端超时后会…...
CPU,内存和硬盘之间的关系
计算机三大件:CPU,内存,硬盘。从运算速度来看,CPU>内存>固态硬盘>机械硬盘。 电脑卡顿怎么解决? 1、清理垃圾; 2、释放C盘空间,因为系统需要C盘空间当作虚拟内存; 3、增…...
Java面试题之基础篇
文章目录 一:谈谈你对面向对象的理解二:JDK、JRE、JVM三者区别和联系三:和equals比较四:hashCode与equals五:final六:String、StringBuffer、StringBuilder七:重载与重写的区别?八&a…...
Bitbucket第一次代码仓库创建/提交/创建新分支/合并分支/忽略ignore
1. 首先要在bitbucket上创建一个项目,这个我没有权限创建,是找的管理员创建的。 管理员创建之后,这个项目给了我权限,我就可以创建我的代码仓库了。 2. 点击这个Projects下的具体项目名字,就会进入这样一个页面&#…...
c#反射用法
在 C# 中,反射是一种能够在运行时检查类型信息、访问属性和调用方法的机制。通过反射,你可以动态地操作类型、对象和程序集,而无需在编译时知道这些类型的具体信息。 反射提供了一组 API,可以让你在运行时获取和操作类型的信息。…...
WPF行为
背景:实现按钮鼠标移动到上方有点交互效果或变一下有阴影。这样使用触发器就行了,但是如果是每个控件都有效果的话使用行为更加合适 1、下载NuGet包:Microsoft.xaml.behavior.wpf 2、创建行为类EffectBehavior,对Behavior进行重写…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
