789. 数的范围 (二分学习)左端大右,右端小左
题目链接
https://www.acwing.com/file_system/file/content/whole/index/content/4317/
当求左端点时,条件是a【mid】大于等于x,并把右端点缩小。
当求右端点时,条件是a【mid】小于等于x,并把左端点扩大。
1.确定一个区间,使得目标值一定在区间中
2.找一个性质满足:
(1)性质具有二段性
(2)答案是二段性的分界点
3.整数二分(处理红色右端点和绿色左端点)


//代码1:右端点
int l=0,r=n;
while(l < r){int mid = (l+r+1) >> 1;if(在红色段){l = mid;}else r = mid - 1;
}
//代码2:左端点绿色
if是绿的,说明ans在【了,m】
int l=0,r=n;
while(l<r){int mid = l+r >> 1;if(是绿的){r = mid;}else l = mid + 1;
}
例题:
在这道题中,因为开始已经求出左端点了,所以求右端点时l可以不动,只更新r为n-1

0402重写:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;
//要求左边界右边界
int n;
int a[100010];
int q;int main()
{scanf("%d%d",&n,&q);for(int i=0;i<n;i++){scanf("%d",&a[i]);}while(q--){int x;scanf("%d",&x);int l=0,r=n-1;while(l<r){int mid = l+r >> 1;if(a[mid] >= x){r = mid;}else{l = mid + 1;}}if(a[l] == x){printf("%d ",l);l = 0;r = n-1;while(l<r){int mid = l+r+1 >> 1;if(a[mid] <= x){l = mid;}else r = mid - 1;}if(a[l] == x){printf("%d\n",l);}}else{printf("-1 -1\n");}}return 0;
}
代码:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>using namespace std;int n,k;
int a[100010];int main()
{scanf("%d%d",&n,&k);for(int i=0;i<n;i++){scanf("%d",&a[i]);}while(k--){int q;scanf("%d",&q);//找区间左端点int l=0,r=n-1;while(l<r){int mid = l+r >> 1;if(a[mid] >= q)//中位数大于q,说明右端点在左半段{r = mid;}else l = mid + 1;}if(a[l] == q){cout<<l<<" ";//右端点l = 0,r = n-1;while(l < r){int mid = (l + r + 1) >> 1;if(a[mid] <= q){l = mid;}else r = mid - 1;}if(a[l] == q){cout<<l<<endl;}}else {cout<<"-1 -1"<<endl;}}return 0;
}相关文章:
789. 数的范围 (二分学习)左端大右,右端小左
题目链接https://www.acwing.com/file_system/file/content/whole/index/content/4317/ 当求左端点时,条件是a【mid】大于等于x,并把右端点缩小。 当求右端点时,条件是a【mid】小于等于x,并把左端点扩大。 1.确定一个区间&…...
docker logs 查找日志常用命令
docker logs 是什么 docker logs 是 Docker 命令行工具提供的一个命令,用于查看容器的日志输出。它可以显示容器在运行过程中生成的标准输出(stdout)和标准错误输出(stderr),帮助用户诊断容器的行为和排查…...
百卓Smart管理平台 importexport.php SQL注入漏洞复现(CVE-2024-27718)
0x01 产品简介 百卓Smart管理平台是北京百卓网络技术有限公司(以下简称百卓网络)的一款安全网关产品,是一家致力于构建下一代安全互联网的高科技企业。 0x02 漏洞概述 百卓Smart管理平台 importexport.php 接口处存在SQL注入漏洞,攻击者除了可以利用 SQL 注入漏洞获取数据…...
PHP教程_PHP5函数str_replace替换字符串中的字符
PHP教程_PHP5函数str_replace替换字符串中的字符 PHP (PHP: Hypertext Preprocessor) 即 “超文本预处理器”, 是在服务器端执行的脚本语言, 尤其适用于Web开发并可嵌入HTML中。 PHP 语法学习了 C语言, 吸纳 Java 和 Perl 多个语言的特色发展出自己的特色语法, 并根据它们的长…...
Word的”交叉引用“和”插入题注“快捷键设置
Word的”交叉引用“和”插入题注“快捷键设置 在MSWord2021中,可以自定义设置快捷键。方法如下:文件-选项-自定义功能区-键盘快捷方式(自定义)。具体过程如图所示。 最后,按照上述流程将插入题注(Insert…...
小白从0学习ctf(web安全)
文章目录 前言一、baby lfi(bugku-CTF)1、简介2、解题思路1、解题前置知识点2、漏洞利用 二、baby lfi 2(bugku-CTF)1.解题思路1、漏洞利用 三、lfi(bugku CTF)1、解题思路1、漏洞利用 总结 前言 此文章是…...
【嵌入式开发 Linux 常用命令系列 7.4 -- awk 处理文件名,去除后缀只保留文件名】
请阅读【嵌入式开发学习必备专栏 】 文章目录 awk 处理文件名,去除后缀只保留文件名 awk 处理文件名,去除后缀只保留文件名 在 shell 中, 可以使用 awk 来处理文件名,去除其后缀。下面是一个示例命令,它会将带有后缀的…...
Linux重点思考(中)--端口/静态内存/负载/日志
这里写目录标题 知道的linux常用命令:查看指定端口进程netstat -pantunetstat -pantu|grep 22 静态运行内存free硬盘物理内存df和du当前负载uptime查看日志awk统计文件每一行单词sed 替换文件单词 知道的linux常用命令:查看指定端口进程 netstat -pantu…...
【Go】五、流程控制
文章目录 1、if2、switch3、for4、for range5、break6、continue7、goto8、return 1、if 条件表达式左右的()是建议省略的if后面一定要有空格,和条件表达式分隔开来{ }一定不能省略if后面可以并列的加入变量的定义 if count : 20;count < 30 {fmt.Println(&quo…...
数据开发-面试真题。
1. 自我介绍 2.在培训班的学过的项目经历 3.之前的工作经历,以及薪资 4.开始讲之前的项目经历 5.技术面试官开始提问。 kafka中进行数据分层,怎么从kafka中实时查询到相关的数据,一条或几条 6.java中的集合,以及io流 7.给定…...
如何使用免费的ChatGpt3.5
如何使用免费的ChatGpt 最近免费的gpt3.5很多都不怎么行了实在是太给力了尾声 最近免费的gpt3.5很多都不怎么行了 原因是什么呢?因为openai已经取消了免费的5刀赠送,那么这些人手上的免费的sses-key 用完后,就基本上全军覆没了,再…...
Kafka硬核干货
目录 Kafka Kafka Producer Kafka Consumer Consumer Offset Log Manager 如何实现高吞吐、低延迟...
分享几个可以免费使用的GPT网站吧
1. ChatGAI ChatGAI是一个界面简洁的AI平台,提供App和网页版,每日均有免费使用机会。 2. ChatGPT 本网站向大家开放了ChatGPT 3.5和4.0版本的免费体验,特别适合新用户。每天都有免费次数,响应迅速,注册便捷࿰…...
MySQL进阶-----前缀索引、单例与联合索引
目录 前言 一、前缀索引 1. 语法 2. 如何选择前缀长度 3. 前缀索引的查询流程 二、单列索引与联合索引 三、索引设计原则 前言 本期是MySQL进阶篇当中索引的最后一期内容,这里我们主要接着上一期继续讲解前缀索引、单例与联合索引。(上一期链接&…...
HTTP——Cookie
HTTP——Cookie 什么是Cookie通过Cookie访问网站 我们之前了解了HTTP协议,如果还有小伙伴还不清楚HTTP协议,可以点击这里: https://blog.csdn.net/qq_67693066/article/details/136895597 我们今天来稍微了解一下HTTP里面一个很小的部分&…...
Scala大数据开发
版权声明 本文原创作者:谷哥的小弟作者博客地址:http://blog.csdn.net/lfdfhl Scala简述 在此,简要介绍 Scala 的基本信息和情况。 Scala释义 Scala 源自于英语单词scalable,表示可伸缩的、可扩展的含义。 Scala作者 Scala编…...
windows无法使用hadoop报错:系统找不到路径
在windows下安装hadoop-3.1.4,进行环境变量配置后,打开window命令行窗口测试hadoop命令,报错,如图所示: 方案:由于JAVA_HOME路径有空格导致,可修改hadoop下\etc\hadoop\hadoop_env.cmd文档中set JAVA_HOME以…...
从0配置React
在本地安装和配置React项目,您可以使用create-react-app这个官方推荐的脚手架工具。以下是安装React的步骤,包括安装Node.js、使用create-react-app创建React应用,以及启动开发服务器。 下载安装node.js运行以下命令,验证Node.js…...
File和IO流
1. File类常用方法 1.1 获取基本属性 • public String getName() :获取名称 • public String getPath() :获取路径 • public String getAbsolutePath():获取绝对路径 • public File getAbsoluteFile():获取绝对路径表示…...
2024系统架构师---解释器架构风格的概念与应用
解释器架构风格是一种软件架构模式,用于构建那些能够读取、解析并执行用户定义的命令或程序代码的系统。这种架构风格的关键在于提供一个运行时环境,它能够理解和执行预定义或用户定义的语言或指令集。通过这种方式,解释器模式能够为特定领域…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...
基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
TJCTF 2025
还以为是天津的。这个比较容易,虽然绕了点弯,可还是把CP AK了,不过我会的别人也会,还是没啥名次。记录一下吧。 Crypto bacon-bits with open(flag.txt) as f: flag f.read().strip() with open(text.txt) as t: text t.read…...
【Ftrace 专栏】Ftrace 参考博文
ftrace、perf、bcc、bpftrace、ply、simple_perf的使用Ftrace 基本用法Linux 利用 ftrace 分析内核调用如何利用ftrace精确跟踪特定进程调度信息使用 ftrace 进行追踪延迟Linux-培训笔记-ftracehttps://www.kernel.org/doc/html/v4.18/trace/events.htmlhttps://blog.csdn.net/…...
