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

789. 数的范围 (二分学习)左端大右,右端小左

题目链接icon-default.png?t=N7T8https://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/ 当求左端点时&#xff0c;条件是a【mid】大于等于x&#xff0c;并把右端点缩小。 当求右端点时&#xff0c;条件是a【mid】小于等于x&#xff0c;并把左端点扩大。 1.确定一个区间&…...

docker logs 查找日志常用命令

docker logs 是什么 docker logs 是 Docker 命令行工具提供的一个命令&#xff0c;用于查看容器的日志输出。它可以显示容器在运行过程中生成的标准输出&#xff08;stdout&#xff09;和标准错误输出&#xff08;stderr&#xff09;&#xff0c;帮助用户诊断容器的行为和排查…...

百卓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中&#xff0c;可以自定义设置快捷键。方法如下&#xff1a;文件-选项-自定义功能区-键盘快捷方式&#xff08;自定义&#xff09;。具体过程如图所示。 最后&#xff0c;按照上述流程将插入题注&#xff08;Insert…...

小白从0学习ctf(web安全)

文章目录 前言一、baby lfi&#xff08;bugku-CTF&#xff09;1、简介2、解题思路1、解题前置知识点2、漏洞利用 二、baby lfi 2&#xff08;bugku-CTF&#xff09;1.解题思路1、漏洞利用 三、lfi&#xff08;bugku CTF&#xff09;1、解题思路1、漏洞利用 总结 前言 此文章是…...

【嵌入式开发 Linux 常用命令系列 7.4 -- awk 处理文件名,去除后缀只保留文件名】

请阅读【嵌入式开发学习必备专栏 】 文章目录 awk 处理文件名&#xff0c;去除后缀只保留文件名 awk 处理文件名&#xff0c;去除后缀只保留文件名 在 shell 中&#xff0c; 可以使用 awk 来处理文件名&#xff0c;去除其后缀。下面是一个示例命令&#xff0c;它会将带有后缀的…...

Linux重点思考(中)--端口/静态内存/负载/日志

这里写目录标题 知道的linux常用命令&#xff1a;查看指定端口进程netstat -pantunetstat -pantu|grep 22 静态运行内存free硬盘物理内存df和du当前负载uptime查看日志awk统计文件每一行单词sed 替换文件单词 知道的linux常用命令&#xff1a;查看指定端口进程 netstat -pantu…...

【Go】五、流程控制

文章目录 1、if2、switch3、for4、for range5、break6、continue7、goto8、return 1、if 条件表达式左右的()是建议省略的if后面一定要有空格&#xff0c;和条件表达式分隔开来{ }一定不能省略if后面可以并列的加入变量的定义 if count : 20;count < 30 {fmt.Println(&quo…...

数据开发-面试真题。

1. 自我介绍 2.在培训班的学过的项目经历 3.之前的工作经历&#xff0c;以及薪资 4.开始讲之前的项目经历 5.技术面试官开始提问。 kafka中进行数据分层&#xff0c;怎么从kafka中实时查询到相关的数据&#xff0c;一条或几条 6.java中的集合&#xff0c;以及io流 7.给定…...

如何使用免费的ChatGpt3.5

如何使用免费的ChatGpt 最近免费的gpt3.5很多都不怎么行了实在是太给力了尾声 最近免费的gpt3.5很多都不怎么行了 原因是什么呢&#xff1f;因为openai已经取消了免费的5刀赠送&#xff0c;那么这些人手上的免费的sses-key 用完后&#xff0c;就基本上全军覆没了&#xff0c;再…...

Kafka硬核干货

目录 Kafka Kafka Producer Kafka Consumer Consumer Offset Log Manager 如何实现高吞吐、低延迟...

分享几个可以免费使用的GPT网站吧

1. ChatGAI ChatGAI是一个界面简洁的AI平台&#xff0c;提供App和网页版&#xff0c;每日均有免费使用机会。 2. ChatGPT 本网站向大家开放了ChatGPT 3.5和4.0版本的免费体验&#xff0c;特别适合新用户。每天都有免费次数&#xff0c;响应迅速&#xff0c;注册便捷&#xff0…...

MySQL进阶-----前缀索引、单例与联合索引

目录 前言 一、前缀索引 1. 语法 2. 如何选择前缀长度 3. 前缀索引的查询流程 二、单列索引与联合索引 三、索引设计原则 前言 本期是MySQL进阶篇当中索引的最后一期内容&#xff0c;这里我们主要接着上一期继续讲解前缀索引、单例与联合索引。&#xff08;上一期链接&…...

HTTP——Cookie

HTTP——Cookie 什么是Cookie通过Cookie访问网站 我们之前了解了HTTP协议&#xff0c;如果还有小伙伴还不清楚HTTP协议&#xff0c;可以点击这里&#xff1a; https://blog.csdn.net/qq_67693066/article/details/136895597 我们今天来稍微了解一下HTTP里面一个很小的部分&…...

Scala大数据开发

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl Scala简述 在此&#xff0c;简要介绍 Scala 的基本信息和情况。 Scala释义 Scala 源自于英语单词scalable&#xff0c;表示可伸缩的、可扩展的含义。 Scala作者 Scala编…...

windows无法使用hadoop报错:系统找不到路径

在windows下安装hadoop-3.1.4,进行环境变量配置后&#xff0c;打开window命令行窗口测试hadoop命令&#xff0c;报错&#xff0c;如图所示&#xff1a; 方案&#xff1a;由于JAVA_HOME路径有空格导致&#xff0c;可修改hadoop下\etc\hadoop\hadoop_env.cmd文档中set JAVA_HOME以…...

从0配置React

在本地安装和配置React项目&#xff0c;您可以使用create-react-app这个官方推荐的脚手架工具。以下是安装React的步骤&#xff0c;包括安装Node.js、使用create-react-app创建React应用&#xff0c;以及启动开发服务器。 下载安装node.js运行以下命令&#xff0c;验证Node.js…...

File和IO流

1. File类常用方法 1.1 获取基本属性 • public String getName() &#xff1a;获取名称 • public String getPath() &#xff1a;获取路径 • public String getAbsolutePath()&#xff1a;获取绝对路径 • public File getAbsoluteFile()&#xff1a;获取绝对路径表示…...

2024系统架构师---解释器架构风格的概念与应用

解释器架构风格是一种软件架构模式&#xff0c;用于构建那些能够读取、解析并执行用户定义的命令或程序代码的系统。这种架构风格的关键在于提供一个运行时环境&#xff0c;它能够理解和执行预定义或用户定义的语言或指令集。通过这种方式&#xff0c;解释器模式能够为特定领域…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...

土建施工员考试:建筑施工技术重点知识有哪些?

《管理实务》是土建施工员考试中侧重实操应用与管理能力的科目&#xff0c;核心考查施工组织、质量安全、进度成本等现场管理要点。以下是结合考试大纲与高频考点整理的重点内容&#xff0c;附学习方向和应试技巧&#xff1a; 一、施工组织与进度管理 核心目标&#xff1a; 规…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...