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

A-B数对(二分查找)

 

#include<bits/stdc++.h>
using namespace std;using ll = long long;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,c;cin>>n>>c;int nu[200000];for(int i=0;i<n;i++){cin>>nu[i]; // 输入数组元素}sort(nu,nu+n);ll cnt=0; // 统计满足条件的数对数量for(int i=0;i<n;i++){ll a=nu[i]+c;int l=0,r=n-1;ll ans=n; // 初始设为数组长度(表示未找到)while(l<=r){int mid=l+(r-l)/2;if(nu[mid]>=a){ans=mid;r=mid-1;}else{l=mid+1;}}l=0,r=n-1;ll res=-1; // 初始设为 -1(表示未找到)while(l<=r){int mid=l+(r-l)/2;if(nu[mid]>a){r=mid-1;} else{res=mid;l=mid+1;}}if(ans<=res){cnt+=res-ans+1;}}cout<<cnt;return 0;}

输入数组 nu 并对其排序,方便后续通过二分查找快速定位数值。

遍历数组中的每个元素 nu[i],计算目标值 a = nu[i] + c,即寻找数组中大于或等于 a 的第一个位置(起始点)和小于或等于 a 的最后一个位置(结束点)。

两次二分查找

  • 第一次二分查找:找到数组中第一个大于等于 a 的位置。
  • 第二次二分查找:找到数组中最后一个小于等于 a 的位置。
  • 两次查找的结果分别是 ansres

数对的数量为区间长度 res - ans + 1

使用 lower_boundupper_bound:

#include<bits/stdc++.h>
using namespace std;using ll = long long;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,c;cin>>n>>c;int nu[200000];for(int i=0;i<n;i++){cin>>nu[i];}sort(nu,nu+n);ll cnt=0;for(int i=0;i<n;i++){ll a=nu[i]+c;ll ans=lower_bound(nu,nu+n,a)-nu;ll res=upper_bound(nu,nu+n,a)-nu-1;if(ans<=res){cnt+=res-ans+1;}}cout<<cnt;return 0;}

lower_bound(nu, nu + n, a) 返回的是第一个大于或等于 a 的元素的迭代器。

upper_bound(nu, nu + n, a) 返回的是第一个大于 a 的元素的迭代器。由于我们需要找的是小于或等于 a 的最大值,因此在计算 res 时,需要减去 1。

  • ans 是第一个大于等于 a 的位置,使用 lower_bound 获取。
  • res 是最后一个小于等于 a 的位置,使用 upper_bound 获取,然后减去 1。

相关文章:

A-B数对(二分查找)

#include<bits/stdc.h> using namespace std;using ll long long;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,c;cin>>n>>c;int nu[200000];for(int i0;i<n;i){cin>>nu[i]; // 输入数组元素}sort(nu,nun);ll cnt0; // 统计满…...

Vue 的各个生命周期

详解 Vue 的各个生命周期 文章目录 详解 Vue 的各个生命周期Vue 组件的生命周期1.1 创建阶段示例&#xff1a; 1.2 挂载阶段示例&#xff1a; 1.3 更新阶段示例&#xff1a; 1.4 销毁阶段示例&#xff1a; 生命周期总结生命周期钩子对比表参考链接 Vue 组件的生命周期 在 Vue …...

实现简易计算器 网格布局 QT环境 纯代码C++实现

问题&#xff1a;通过代码完成一个10以内加减法计算器。不需要自适应&#xff0c;界面固定360*350。 ""按钮90*140&#xff0c;其它按钮90*70。 参考样式 #define DEFULT_BUTTON_STYLE "\ QPushButton{\color:#000000;\border:1px solid #AAAAAA;\border-radi…...

后端开发详细学习框架与路线

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;后端开发 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 为帮助你合理安排时间&#xff0c;以下是结合上述学习内容的阶段划分与时间分配建议。时间安排灵活&a…...

2.langchain中的prompt模板 (FewShotPromptTemplate)

本教程将介绍如何使用 LangChain 库中的 PromptTemplate 和 FewShotPromptTemplate 来构建和运行提示&#xff08;prompt&#xff09;&#xff0c;并通过示例数据展示其应用。 安装依赖 首先&#xff0c;确保你已经安装了 langchain 和相关依赖&#xff1a; pip install lan…...

FairGuard游戏加固实机演示

此前&#xff0c;FairGuard对市面上部分游戏遭遇破解的案例进行了详细分析&#xff0c;破解者会采用静态分析与动态调试相结合的手段&#xff0c;逆向分析出代码逻辑并对其进行篡改&#xff0c;实现作弊功能&#xff0c;甚至是对游戏资源文件进行篡改&#xff0c;从而制售外挂。…...

Spark使用过程中的 15 个常见问题、详细解决方案

目录 问题 1&#xff1a;Spark 作业超时问题描述解决方案Python 实现 问题 2&#xff1a;内存溢出问题描述解决方案Python 实现 问题 3&#xff1a;Shuffle 性能问题问题描述解决方案Python 实现 问题 4&#xff1a;Spark 作业调度不均问题描述解决方案Python 实现 问题 5&…...

算法【最长递增子序列问题与扩展】

本文讲解最长递增子序列以及最长不下降子序列的最优解&#xff0c;以及一些扩展题目。本文中讲述的是最优解&#xff0c;时间复杂度是O(n*logn)&#xff0c;空间复杂度O(n)&#xff0c;好实现、理解难度不大。这个问题也可以用线段树来求解&#xff0c;时间和空间复杂度和本节讲…...

k8s篇之flannel网络模型详解

在 Kubernetes (K8s) 中,Flannel 是一种常用的网络插件,用于实现容器之间的网络通信。Flannel 提供了一种覆盖网络(Overlay Network)模型,使得容器可以跨多个主机进行通信。 以下是 Flannel 在 Kubernetes 中的详细工作原理和覆盖网络模型的详解: 1.Flannel 简介 Flann…...

windows 和 linux检查操作系统基本信息

windows检查操作系统基本信息 systeminfolinux检查操作系统基本信息 获取系统位数 getconf LONG_BIT查询操作系统release信息 lsb_release -a查询系统信息 cat /etc/issue查询系统名称 uname -a...

Oracle OCP认证考试考点详解082系列22

题记&#xff1a; 本系列主要讲解Oracle OCP认证考试考点&#xff08;题目&#xff09;&#xff0c;适用于19C/21C,跟着学OCP考试必过。 105. 第105题&#xff1a; 题目 解析及答案&#xff1a; 题目翻译&#xff1a; 关于Oracle数据库中的事务请选择两个正确的陈述&#xf…...

线性回归 - 最小二乘法

线性回归 一 简单的线性回归应用 webrtc中的音视频同步。Sender Report数据包 NTP Timestamp&#xff08;网络时间协议时间戳&#xff09;&#xff1a;这是一个64位的时间戳&#xff0c;记录着发送SR的NTP时间戳&#xff0c;用于同步不同源之间的时间。RTP Timestamp&#xff1…...

Linux - 线程基础

文章目录 1.什么是线程2.线程vs进程3.线程调度4.线程控制4.1 POSIX线程库4.2创建线程4.3线程终止4.4线程等待4.5线程分离 5、线程封装 1.什么是线程 在Linux操作系统中&#xff0c;线程是进程内部的一个执行流。在Linux操作系统下&#xff0c;执行流统称为轻量级进程&#xff0…...

网络爬虫——分布式爬虫架构

分布式爬虫在现代大数据采集中是不可或缺的一部分。随着互联网信息量的爆炸性增长&#xff0c;单机爬虫在性能、效率和稳定性上都面临巨大的挑战。分布式爬虫通过任务分发、多节点协作以及结果整合&#xff0c;成为解决大规模数据抓取任务的核心手段。 本节将从 Scrapy 框架的…...

RT_Thread内核源码分析(三)——线程

目录 1. 线程结构 2. 线程创建 2.1 静态线程创建 2.2 动态线程创建 2.3 源码分析 2.4 线程内存结构 3. 线程状态 3.1 线程状态分类 3.2 就绪状态和运行态 3.3 阻塞/挂起状态 3.3.1 阻塞工况 3.4 关闭状态 3.4.1 线程关闭接口 3.4.2 静态线程关闭 3.4.3 动态线程关…...

正排索引和倒排索引

一、简介 正排索引&#xff1a;一个未经处理的数据库中&#xff0c;一般是以文档ID作为索引&#xff0c;以文档内容作为记录。 倒排索引&#xff1a;Inverted index&#xff0c;指的是将单词或记录作为索引&#xff0c;将文档ID作为记录&#xff0c;这样便可以方便地通过单词或…...

丹摩 | 重返丹摩(上)

目录 一.登录平台 二. 数据管理与预处理 1.数据清洗 2.数据格式转换 3.特征工程 二.数据可视化 1.快速可视化 2.数据洞察 3.自定义视图 三.技术支持与帮助 1.技术支持 (1). 帮助文档 (2). 用户社区 2.客服支持 (1). 在线客服 (2). 反馈与建议 总结 一.登录平台…...

Frontend - 防止多次请求,避免重复请求

目录 一、避免重复执行的多种情况 &#xff08;一&#xff09;根据用途 &#xff08;二&#xff09;根据用户操作 二、具体实现 &#xff08;一&#xff09;“Ajax ”结合disabled (防止多次请求)&#xff0c;避免多次点击重复请求 1. 适用场景 2. 解决办法 3. 示例 &…...

RHCE的学习(22)

第四章 流程控制之条件判断 条件判断语句是一种最简单的流程控制语句。该语句使得程序根据不同的条件来执行不同的程序分支。本节将介绍Shell程序设计中的简单的条件判断语句。 if语句语法 单分支结构 # 语法1&#xff1a; if <条件表达式> then指令 fi #语法2&#x…...

【前端知识】简单讲讲什么是微前端

微前端介绍 一、定义二、背景三、核心思想四、基本要素五、核心价值六、实现方式七、应用场景八、挑战与解决方案 什么是single-spa一、核心特点二、核心原理三、应用加载流程四、最佳实践五、优缺点六、应用场景 什么是 qiankun一、概述二、特点与优势三、核心功能四、使用场景…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容&#xff1a;参考网站&#xff1a; PID算法控制 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...