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
的位置。 - 两次查找的结果分别是
ans
和res
。
数对的数量为区间长度 res - ans + 1
使用 lower_bound
和 upper_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 创建阶段示例: 1.2 挂载阶段示例: 1.3 更新阶段示例: 1.4 销毁阶段示例: 生命周期总结生命周期钩子对比表参考链接 Vue 组件的生命周期 在 Vue …...

实现简易计算器 网格布局 QT环境 纯代码C++实现
问题:通过代码完成一个10以内加减法计算器。不需要自适应,界面固定360*350。 ""按钮90*140,其它按钮90*70。 参考样式 #define DEFULT_BUTTON_STYLE "\ QPushButton{\color:#000000;\border:1px solid #AAAAAA;\border-radi…...

后端开发详细学习框架与路线
🚀 作者 :“码上有前” 🚀 文章简介 :后端开发 🚀 欢迎小伙伴们 点赞👍、收藏⭐、留言💬 为帮助你合理安排时间,以下是结合上述学习内容的阶段划分与时间分配建议。时间安排灵活&a…...

2.langchain中的prompt模板 (FewShotPromptTemplate)
本教程将介绍如何使用 LangChain 库中的 PromptTemplate 和 FewShotPromptTemplate 来构建和运行提示(prompt),并通过示例数据展示其应用。 安装依赖 首先,确保你已经安装了 langchain 和相关依赖: pip install lan…...

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

Spark使用过程中的 15 个常见问题、详细解决方案
目录 问题 1:Spark 作业超时问题描述解决方案Python 实现 问题 2:内存溢出问题描述解决方案Python 实现 问题 3:Shuffle 性能问题问题描述解决方案Python 实现 问题 4:Spark 作业调度不均问题描述解决方案Python 实现 问题 5&…...

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

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
题记: 本系列主要讲解Oracle OCP认证考试考点(题目),适用于19C/21C,跟着学OCP考试必过。 105. 第105题: 题目 解析及答案: 题目翻译: 关于Oracle数据库中的事务请选择两个正确的陈述…...

线性回归 - 最小二乘法
线性回归 一 简单的线性回归应用 webrtc中的音视频同步。Sender Report数据包 NTP Timestamp(网络时间协议时间戳):这是一个64位的时间戳,记录着发送SR的NTP时间戳,用于同步不同源之间的时间。RTP Timestamp࿱…...

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

网络爬虫——分布式爬虫架构
分布式爬虫在现代大数据采集中是不可或缺的一部分。随着互联网信息量的爆炸性增长,单机爬虫在性能、效率和稳定性上都面临巨大的挑战。分布式爬虫通过任务分发、多节点协作以及结果整合,成为解决大规模数据抓取任务的核心手段。 本节将从 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 动态线程关…...

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

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

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

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

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

AWS IAM
一、介绍 1、简介 AWS Identity and Access Management (IAM) 是 Amazon Web Services 提供的一项服务,用于管理 AWS 资源的访问权限。通过 IAM,可以安全地控制用户、组和角色对 AWS 服务和资源的访问权限。IAM 是 AWS 安全模型的核心组成部分,确保只有经过授权的用户和应…...

丹摩|丹摩助力selenium实现大麦网抢票
丹摩|丹摩助力selenium实现大麦网抢票 声明:非广告,为用户体验 1.引言 在人工智能飞速发展的今天,丹摩智算平台(DAMODEL)以其卓越的AI算力服务脱颖而出,为开发者提供了一个简化AI开发流程的强…...

基于Qt/C++/Opencv实现的一个视频中二维码解析软件
本文详细讲解了如何利用 Qt 和 OpenCV 实现一个可从视频和图片中检测二维码的软件。代码实现了视频解码、多线程处理和界面更新等功能,是一个典型的跨线程图像处理项目。以下分模块对代码进行解析。 一、项目的整体结构 项目分为以下几部分: 主窗口 (M…...

智慧理财项目测试文档
目录 幕布思维导图链接:https://www.mubu.com/doc/6xk3c7DzgFs学习链接:https://www.bilibili.com/video/BV15J4m147vZ/?spm_id_from333.999.0.0&vd_source078d5d025b9cb472d70d8fda1a7dc5a6智慧理财项目测试文档项目介绍项目基本信息项目业务特性系…...

R | 统一栅格数据的坐标系、分辨率和行列号
各位同学,在做相关性等分析时,经常会遇到各栅格数据间的行列号不统一等问题,下面的代码能直接解决这类麻烦。以某个栅格数据的坐标系、分辨率和行列号为准,统一文件夹内所有栅格并输出到新的文件夹。 代码只需要更改输入输出和ti…...

C++学习——编译的过程
编译的过程——预处理 引言预处理包含头文件宏定义指令条件编译 编译、链接 引言 C程序编译的过程:预处理 -> 编译(优化、汇编)-> 链接 编译和链接的内容可以查阅这篇文章(点击查看) 预处理 编译预处理是指&a…...

当你要改文件 但是原来的文件内容又不能丢失的时候,拷贝一份(备注原来的),然后添加后缀:.bak
当你要改文件 但是原来的文件内容又不能丢失的时候,拷贝一份(备注原来的),然后添加后缀:.bak !!!文件不要直接删除,若你以后要还原的话会找不到...

MATLAB神经网络(五)——R-CNN视觉检测
5.1 目标分类、检测与分割 在计算机视觉领域,目标分类、检测与分割是常用计数。三者的联系与区分又在哪呢?目标分类是解决图像中的物体是什么的问题;目标检测是解决图像中的物体是什么,在哪里的问题;目标分割时将目标和…...

mock.js:定义、应用场景、安装、配置、使用
前言:什么是mock.js? 作为一个前端程序员,没有mockjs你不感觉很被动吗?你不感觉你的命脉被后端那个男人掌握了吗?所以,我命由我不由天!学学mock.js吧! mock.js 是一个用于生成随机…...

【GAT】 代码详解 (1) 运行方法【pytorch】可运行版本
GRAPH ATTENTION NETWORKS 代码详解 前言0.引言1. 环境配置2. 代码的运行2.1 报错处理2.2 运行结果展示 3.总结 前言 在前文中,我们已经深入探讨了图卷积神经网络和图注意力网络的理论基础。还没看的同学点这里补习下。接下来,将开启一个新的阶段&#…...