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

ABC364:D - K-th Nearest(二分)

题目

在一条数线上有 N+QN+Q 个点 A1,…,AN,B1,…,BQA1​,…,AN​,B1​,…,BQ​ ,其中点 AiAi​ 的坐标为 aiai​ ,点 BjBj​ 的坐标为 bjbj​ 。

就每个点 j=1,2,…,Qj=1,2,…,Q 回答下面的问题:

  • 设 XX 是 A1,A2,…,ANA1​,A2​,…,AN​ 中最接近点 BjBj​ 的 kjkj​ -th 点。求点 XX 与 BjBj​ 之间的距离。更正式地说,设 didi​ 是点 AiAi​ 与 BjBj​ 之间的距离。将 (d1,d2,…,dN)(d1​,d2​,…,dN​) 按升序排序,得到序列 (d1′,d2′,…,dN′)(d1′​,d2′​,…,dN′​) 。求 dkj′dkj​′​ .
限制因素
  • 1≤N,Q≤1051≤N,Q≤105
  • −108≤ai,bj≤108−108≤ai​,bj​≤108
  • 1≤kj≤N1≤kj​≤N
  • 所有输入值均为整数。
做法

题目就是让我们求离b的第k近的距离是多少。我们的思路就是给a排序,然后找到b所在的位置,然后往b的左右两边算他的第k近的数。但这样往b的左右两边一个一个看会超时。我们就二分b往两边的距离,看a数组有多少个在b-mid到b+mid的范围内。如果个数小于k,那么范围小了,l=mid,否则r=mid。最后输出r即可。

#include<bits/stdc++.h> 
using namespace std;
int n,q;
long long a[100010];
int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);sort(a+1,a+1+n);for(int i=1;i<=q;i++){long long b;int k;scanf("%lld%d",&b,&k);if(b<=a[1]){//特判cout<<abs(b-a[k])<<endl;continue;}else if(b>=a[n]){cout<<abs(b-a[n+1-k])<<endl;continue;}long long l=-1e18-10,r=1e18+10;//也可以不用这么大,2e8就行while(l+1<r){long long mid=l+(r-l)/2;int id1=lower_bound(a+1,a+1+n,b-mid)-a;int id2=upper_bound(a+1,a+1+n,b+mid)-a;if(id2-id1>=k){r=mid;}else{l=mid;}}cout<<r<<endl;}
}

相关文章:

ABC364:D - K-th Nearest(二分)

题目 在一条数线上有 NQNQ 个点 A1,…,AN,B1,…,BQA1​,…,AN​,B1​,…,BQ​ &#xff0c;其中点 AiAi​ 的坐标为 aiai​ &#xff0c;点 BjBj​ 的坐标为 bjbj​ 。 就每个点 j1,2,…,Qj1,2,…,Q 回答下面的问题&#xff1a; 设 XX 是 A1,A2,…,ANA1​,A2​,…,AN​ 中最…...

hive中分区与分桶的区别

过去&#xff0c;在学习hive的过程中学习过分桶与分区。但是&#xff0c;却未曾将分区与分桶做详细比较。今天&#xff0c;回顾skew join时涉及到了分桶这一概念&#xff0c;一时间无法区分出分区与分桶的区别。查阅资料&#xff0c;特地记录下来。 一、Hive分区 1.分区一般是…...

Blender材质-PBR与纹理材质

1.PBR PBR:Physically Based Rendering 基于物理的渲染 BRDF:Bidirection Reflectance Distribution Function 双向散射分散函数 材质着色操作如下图&#xff1a; 2.纹理材质 左上角&#xff1a;编辑器类型中选择&#xff0c;着色器编辑器 新建着色器 -> 新建纹理 -> 新…...

微软的Edge浏览器如何设置兼容模式

微软的Edge浏览器如何设置兼容模式&#xff1f; Microsoft Edge 在浏览部分网站的时候&#xff0c;会被标记为不兼容&#xff0c;会有此网站需要Internet Explorer的提示&#xff0c;虽然可以手动点击在 Microsoft Edge 中继续浏览&#xff0c;但是操作起来相对复杂&#xff0c…...

SpringBoot开启多端口探究(1)

文章目录 前情提要发散探索从management.port开始确定否需要开启额外端口额外端口是如何开启的ManagementContextFactory的故事从哪儿来创建过程 management 相关API如何被注册 小结 前情提要 最近遇到一个需求&#xff0c;在单个服务进程上开启多网络端口&#xff0c;将API的…...

优化算法:2.粒子群算法(PSO)及Python实现

一、定义 粒子群算法&#xff08;Particle Swarm Optimization&#xff0c;PSO&#xff09;是一种模拟鸟群觅食行为的优化算法。想象一群鸟在寻找食物&#xff0c;每只鸟都在尝试找到食物最多的位置。它们通过互相交流信息&#xff0c;逐渐向食物最多的地方聚集。PSO就是基于这…...

ThreadLocal面试三道题

针对ThreadLocal的面试题&#xff0c;我将按照由简单到困难的顺序给出三道题目&#xff0c;并附上参考答案的概要。 1. 简单题&#xff1a;请简述ThreadLocal是什么&#xff0c;以及它的主要作用。 参考答案&#xff1a; ThreadLocal是Java中的一个类&#xff0c;用于提供线…...

Git操作指令(已完结)

Git操作指令 一、安装git 1、设置配置信息&#xff1a; # global全局配置 git config --global user.name "Your username" git config --global user.email "Your email"# 显示颜色 git config --global color.ui true# 配置别名&#xff0c;各种指令都…...

大数据采集工具——Flume简介安装配置使用教程

Flume简介&安装配置&使用教程 1、Flume简介 一&#xff1a;概要 Flume 是一个可配置、可靠、高可用的大数据采集工具&#xff0c;主要用于将大量的数据从各种数据源&#xff08;如日志文件、数据库、本地磁盘等&#xff09;采集到数据存储系统&#xff08;主要为Had…...

C语言 #具有展开功能的排雷游戏

文章目录 前言 一、整个排雷游戏的思维梳理 二、整体代码分布布局 三、游戏主体逻辑实现--test.c 四、整个游戏头文件的引用以及函数的声明-- game.h 五、游戏功能的具体实现 -- game.c 六、老六版本 总结 前言 路漫漫其修远兮&#xff0c;吾将上下而求索。 一、整个排…...

npm publish出错,‘proxy‘ config is set properly. See: ‘npm help config‘

问题&#xff1a;使用 npm publish发布项目依赖失败&#xff0c;报错 proxy config is set properly. See: npm help config 1、先查找一下自己的代理 npm config get proxy npm config get https-proxy npm config get registry2、然后将代理和缓存置空 方式一&#xff1a; …...

Springboot 多数据源事务

起因 在一个service方法上使用的事务,其中有方法是调用的多数据源orderDB 但是多数据源没有生效,而是使用的primaryDB 原因 spring 事务实现的方式 以 Transactional 注解为例 (也可以看 TransactionTemplate&#xff0c; 这个流程更简单一点)。 入口&#xff1a;ProxyTransa…...

Python每日学习

我是从c转来学习Python的&#xff0c;总感觉和c相比Python的实操简单&#xff0c;但是由于写c的代码多了&#xff0c;感觉Python的语法好奇怪 就比如说c的开头要有库&#xff08;就是类似于#include <bits/stdc.h>&#xff09;而且它每一项的代码结束之后要有一个表示结…...

数据库 执行sql添加删除字段

添加字段&#xff1a; ALTER TABLE 表明 ADD COLUMN 字段名 类型 DEFAULT NULL COMMENT 注释 AFTER 哪个字段后面; 效果&#xff1a; 删除字段&#xff1a; ALTER TABLE 表明 DROP COLUMN 字段;...

前端开发:HTML与CSS

文章目录 前言1.1、CS架构和BS架构1.2、网页构成 HTML1.web开发1.1、最简单的web应用程序1.2、HTTP协议1.2.1 、简介1.2.2、 http协议特性1.3.3、http请求协议与响应协议 2.HTML概述3.HTML标准结构4.标签的语法5.基本标签6.超链接标签6.1、超链接基本使用6.2、锚点 7.img标签8.…...

ctfshow解题方法

171 172 爆库名->爆表名->爆字段名->爆字段值 -1 union select 1,database() ,3 -- //返回数据库名 -1 union select 1,2,group_concat(table_name) from information_schema.tables where table_schema库名 -- //获取数据库里的表名 -1 union select 1,group_concat(…...

探索 Blockly:自定义积木实例

3.实例 3.1.基础块 无输入 , 无输出 3.1.1.json var textOneJson {"type": "sql_test_text_one","message0": " one ","colour": 30,"tooltip": 无输入 , 无输出 };javascriptGenerator.forBlock[sql_test_te…...

MongoDB教程(二十三):关于MongoDB自增机制

&#x1f49d;&#x1f49d;&#x1f49d;首先&#xff0c;欢迎各位来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里不仅可以有所收获&#xff0c;同时也能感受到一份轻松欢乐的氛围&#xff0c;祝你生活愉快&#xff01; 文章目录 引言一、MongoD…...

展馆导览系统架构解析,从需求分析到上线运维

在物质生活日益丰富的当下&#xff0c;人们对精神世界的追求愈发强烈&#xff0c;博物馆、展馆、纪念馆等场所成为人们丰富知识、滋养心灵的热门选择。与此同时&#xff0c;人们对展馆的导航体验也提出了更高要求&#xff0c;展馆导览系统作为一种基于室内外地图相结合的位置引…...

Servlet详解(超详细)

Servlet详解 文章目录 Servlet详解一、基本概念二、Servlet的使用1、创建Servlet类2、配置Servleta. 使用web.xml配置b. 使用注解配置 3、部署Web应用4、处理HTTP请求和生成响应5、处理表单数据HTML表单Servlet 6、管理会话 三、servlet生命周期1、加载和实例化2、初始化3、 请…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

K8S认证|CKS题库+答案| 11. AppArmor

目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作&#xff1a; 1&#xff09;、切换集群 2&#xff09;、切换节点 3&#xff09;、切换到 apparmor 的目录 4&#xff09;、执行 apparmor 策略模块 5&#xff09;、修改 pod 文件 6&#xff09;、…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...