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

ABC318 F - Octopus

解题思路

  • 对于每个宝藏维护n个区间(x-l_i-1,x+l_i],答案一定在这些区间中
  • 对于每个区间的端点由小到大排序
  • 对于每个点进行判断,若当前位置合法,则该点一定为一个右端点
  • 则该点到前一个端点之间均为合法点
  • 若前一个点不合法,则一定是某一个区间限制的左端点,所以该点到这个端点之间均未超出范围,使某一宝藏取不到
  • 若前一个点合法,则在满足的前提下,还避免了重复
import java.io.*;
import java.math.BigInteger;
import java.util.*;//implements Runnable
public class Main {static long md=(long)998244353;static long Linf=Long.MAX_VALUE/2;static int inf=Integer.MAX_VALUE/2;static int N=200010;static int n=0;static int m=0;static long ans=0;static long[] a;static long[] b;static boolean check(long x){PriorityQueue<Long> q=new PriorityQueue<>((o1,o2)->{if(o1-o2>0)return 1;else if(o1-o2<0)return -1;else return 0;});for(int i=1;i<=n;++i){q.add(Math.abs(x-a[i]));}for(int i=1;i<=n;++i){if(q.poll()>b[i])return false;}return true;}static void solve() throws Exception{AReader input=new AReader();
//        String fileName="C:\\Users\\Lenovo\\Downloads\\055.txt";
//		Scanner input=new Scanner(new FileReader(fileName));//        BufferedReader input = new BufferedReader(new FileReader(fileName));PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));String al="abcdefghijklmnopqrstuvwxyz";char[] ac=al.toCharArray();n=input.nextInt();a=new long[n+1];for(int i=1;i<=n;++i)a[i]=input.nextLong();b=new long[n+1];for(int i=1;i<=n;++i)b[i]=input.nextLong();Arrays.sort(b,1,n+1);TreeSet<Long> hs=new TreeSet<>();for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){hs.add(a[i]-b[j]-1);//左端点,左开右闭,区分左端点和右端点hs.add(a[i]+b[j]);//右端点}}long l=0;for(long x:hs){if(check(x))ans+=x-l;l=x;//左端点,要么是右端点区间去重叠}out.println(ans);out.flush();out.close();}public static void main(String[] args) throws Exception{solve();}//	public static final void main(String[] args) throws Exception {
//		  new Thread(null, new Tx2(), "线程名字", 1 << 27).start();
//	}
//		@Override
//		public void run() {
//			try {
//				//原本main函数的内容
//				solve();
//
//			} catch (Exception e) {
//			}
//		}staticclass AReader{BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bf=new BufferedReader(new InputStreamReader(System.in));st=new StringTokenizer("");bw=new BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}public char nextChar() throws IOException{//确定下一个token只有一个字符的时候再用return next().charAt(0);}public int nextInt() throws IOException{return Integer.parseInt(next());}public long nextLong() throws IOException{return Long.parseLong(next());}public double nextDouble() throws IOException{return Double.parseDouble(next());}public float nextFloat() throws IOException{return Float.parseFloat(next());}public byte nextByte() throws IOException{return Byte.parseByte(next());}public short nextShort() throws IOException{return Short.parseShort(next());}public BigInteger nextBigInteger() throws IOException{return new BigInteger(next());}public void println() throws IOException {bw.newLine();}public void println(int[] arr) throws IOException{for (int value : arr) {bw.write(value + " ");}println();}public void println(int l, int r, int[] arr) throws IOException{for (int i = l; i <= r; i ++) {bw.write(arr[i] + " ");}println();}public void println(int a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(int a) throws IOException{bw.write(String.valueOf(a));}public void println(String a) throws IOException{bw.write(a);bw.newLine();}public void print(String a) throws IOException{bw.write(a);}public void println(long a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(long a) throws IOException{bw.write(String.valueOf(a));}public void println(double a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}public void print(double a) throws IOException{bw.write(String.valueOf(a));}public void print(char a) throws IOException{bw.write(String.valueOf(a));}public void println(char a) throws IOException{bw.write(String.valueOf(a));bw.newLine();}}
}

 

相关文章:

ABC318 F - Octopus

解题思路 对于每个宝藏维护个区间&#xff0c;答案一定在这些区间中对于每个区间的端点由小到大排序对于每个点进行判断&#xff0c;若当前位置合法&#xff0c;则该点一定为一个右端点则该点到前一个端点之间均为合法点若前一个点不合法&#xff0c;则一定是某一个区间限制的…...

Docker实战教程 第3章 Dockerfile

4-2 通过dockerfile制作镜像 需求 制作一个具有ping ip ifconfig vim 这些命令工具的一个nginx镜像&#xff0c;通过dockerfile完成STEP1 : 写一个Dockerfile FROM nginx # 基于一个基础镜像 RUN lsstep2 docker build . -f 指定使用的dockerfile来生成镜像-t 指定镜像名…...

JSON在量化交易系统中的应用

JSON在量化交易系统中的应用场景 数据传输和存储&#xff1a;JSON可以将交易数据以结构化的方式进行编码&#xff0c;并将其转换为字符串进行传输和存储。这样可以方便地在不同的系统之间传递数据&#xff0c;并且可以保持数据的完整性和一致性。 API通信&#xff1a;量化交易…...

x-cmd-pkg | broot 是基于 Rust 开发的一个终端文件管理器

简介 broot 是基于 Rust 开发的一个终端文件管理器&#xff0c;它设计用于帮助用户在终端中更轻松地管理文件和目录&#xff0c;使用树状视图探索文件层次结构、操作文件、启动操作以及定义您自己的快捷方式。 同时它还集成了 ls, tree, find, grep, du, fzf 等工具的常用功能…...

设置asp.net core WebApi函数请求参数可空的两种方式

以下面定义的asp.net core WebApi函数为例&#xff0c;客户端发送申请时&#xff0c;默认三个参数均为必填项&#xff0c;不填会报错&#xff0c;如下图所示&#xff1a; [HttpGet] public string GetSpecifyValue(string param1,string param2,string param3) {return $"…...

Vue.js组件精讲 开篇:Vue.js的精髓——组件

写在前面 Vue.js&#xff0c;无疑是当下最火热的前端框架 Almost&#xff0c;而 Vue.js 最精髓的&#xff0c;正是它的组件与组件化。写一个 Vue 工程&#xff0c;也就是在写一个个的组件。 业务场景是千变万化的&#xff0c;而不变的是 Vue.js 组件开发的核心思想和使用技巧…...

R语言中的常用数据结构

目录 R对象的基本类型 R对象的属性 R的数据结构 向量 矩阵 数组 列表 因子 缺失值NA 数据框 R的数据结构总结 R语言可以进行探索性数据分析&#xff0c;统计推断&#xff0c;回归分析&#xff0c;机器学习&#xff0c;数据产品开发 R对象的基本类型 R语言对象有五…...

基于Python的微博旅游情感分析、微博舆论可视化系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

机器学习的模型校准

背景知识 之前一直没了解过模型校准是什么东西&#xff0c;最近上班业务需要看了一下&#xff1a; 模型校准是指对分类模型进行修正以提高其概率预测的准确性。在分类模型中&#xff0c;预测结果通常以类别标签形式呈现&#xff08;例如&#xff0c;0或1&#xff09;&#xf…...

0.17元的4位数码管驱动芯片AiP650,支持键盘,还是无锡国家集成电路设计中心某公司的

推荐原因&#xff1a;便宜的4位数码管驱动芯片 只要0.17元&#xff0c;香吗&#xff1f;X背景的哦。 2 线串口共阴极 8 段 4 位 LED 驱动控制/7*4 位键盘扫描专用电路 AIP650参考电路图 AIP650引脚定义...

【C++】编程规范之内存规则

在高质量编程中&#xff0c;内存管理是一个至关重要的方面。主要有以下原则&#xff1a; 内存分配后需要检查是否成功&#xff1a;内存分配可能会失败&#xff0c;特别是在内存紧张的情况下。因此&#xff0c;在分配内存后&#xff0c;应该检查分配是否成功。 int* ptr new …...

并发编程之线程池的应用以及一些小细节的详细解析

线程池在实际中的使用 实际开发中&#xff0c;最常用主要还是利用ThreadPoolExecutor自定义线程池&#xff0c;可以给出一些关键的参数来自定义。 在下面的代码中可以看到&#xff0c;该线程池的最大并行线程数是5&#xff0c;线程等候区&#xff08;阻塞队列)是3&#xff0c;即…...

基于JSP的农产品供销服务系统

背景 互联网的迅猛扩张彻底革新了全球各类组织的运营模式。自20世纪90年代起&#xff0c;中国的政府机关和各类企业便开始探索利用网络系统来处理管理事务。然而&#xff0c;早期的网络覆盖范围有限、用户接受度不高、互联网相关法律法规不完善以及技术开发不够成熟等因素&…...

redis之主从复制、哨兵模式

一 redis群集有三种模式 主从复制&#xff1a; 主从复制是高可用Redis的基础&#xff0c;哨兵和集群都是在主从复制基础上实现高可用的。 主从复制主要实现了数据的多机备份&#xff0c;以及对于读操作的负载均衡和简单的故障恢复。 缺陷&#xff1a; 故障恢复无法自动化&…...

【随笔】Git 基础篇 -- 分支与合并 git rebase(十)

&#x1f48c; 所属专栏&#xff1a;【Git】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#x1f496; 欢迎大…...

图像识别技术在体育领域的应用

图像识别技术在体育领域的应用是一个充满创新和挑战的研究方向。随着计算机视觉和人工智能技术的快速发展&#xff0c;图像识别技术已经在体育领域展现出广泛的应用潜力和实际价值。以下是一些图像识别技术在体育领域的具体应用&#xff1a; 运动员表现分析&#xff1a; 图像识…...

【项目新功能开发篇】开发编码

作者介绍&#xff1a;本人笔名姑苏老陈&#xff0c;从事JAVA开发工作十多年了&#xff0c;带过大学刚毕业的实习生&#xff0c;也带过技术团队。最近有个朋友的表弟&#xff0c;马上要大学毕业了&#xff0c;想从事JAVA开发工作&#xff0c;但不知道从何处入手。于是&#xff0…...

软件设计原则:开闭原则

定义 开闭原则&#xff08;Open-Closed Principle, OCP&#xff09;是面向对象设计的基本原则之一&#xff0c;由 Bertrand Meyer 提出。它指出软件实体&#xff08;类、模块、函数等&#xff09;应该对扩展开放&#xff0c;对修改封闭。这意味着软件应该设计成在不修改现有代…...

Python如何下载视频

大家好&#xff0c;今天我将为大家介绍如何使用Python来下载视频。Python作为一门强大的编程语言&#xff0c;不仅可以用于数据分析、机器学习等领域&#xff0c;还能用于网络爬虫和视频下载等任务。下面我将详细介绍如何使用Python来下载视频。 首先&#xff0c;我们需要明确…...

使用虚拟引擎为AR体验提供动力

Powering AR Experiences with Unreal Engine ​​​​​​​ 目录 1. 虚拟引擎概述 2. 虚拟引擎如何为AR体验提供动力 3. 虚拟引擎中AR体验的组成部分是什么&#xff1f; 4. 使用虚拟引擎创建AR体验 5. 虚拟引擎中AR的优化提示 6. 将互动性融入AR与虚拟引擎 7. 在AR中…...

独立语音AI创业必读,ElevenLabs Independent计划全链路解析:从白名单内测→额度扩容→月度用量审计→续期失败预警

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;ElevenLabs Independent计划的战略定位与生态价值 ElevenLabs Independent 计划并非单纯的技术授权项目&#xff0c;而是面向独立开发者、开源创作者与小型 AI 应用团队构建的可持续协作基础设施。其核…...

液态硅胶注塑加工供应商推荐

随着液态硅胶&#xff08;LSR&#xff09;在医疗、母婴、电子、汽车等多个领域的广泛应用&#xff0c;选择一个可靠的液态硅胶注塑加工供应商变得至关重要。作为天沅智能制造科技有限公司&#xff08;简称TYM&#xff09;&#xff0c;我们不仅深耕于液态硅胶注射成型机械的设计…...

Encaustic不是滤镜!揭秘热蜡媒介物理特性如何反向重构MJ提示词结构:材料科学×AIGC的跨学科实践

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;Encaustic不是滤镜&#xff01;——热蜡媒介的本质祛魅 Encaustic&#xff08;热蜡绘画&#xff09;常被误认为是数字图像处理中的一种“复古滤镜”&#xff0c;实则是一种拥有两千多年历史的实体绘画媒…...

Shinkai Node:无代码AI智能体平台架构解析与实战部署

1. 项目概述&#xff1a;Shinkai Node&#xff0c;一个无需代码的AI智能体构建平台 最近在折腾AI智能体&#xff08;AI Agent&#xff09;的时候&#xff0c;发现了一个挺有意思的开源项目—— Shinkai Node 。它来自dcSpark团队&#xff0c;核心目标非常明确&#xff1a; …...

LIO-SAM源码逐行解析:从因子图构建到多传感器融合实战

1. LIO-SAM技术架构解析 LIO-SAM&#xff08;Lidar Inertial Odometry via Smoothing and Mapping&#xff09;是Tixiao Shan博士在LeGO-LOAM基础上开发的激光-惯性紧耦合SLAM系统。它的核心创新点在于采用因子图优化框架&#xff0c;将IMU预积分、激光里程计、GPS和闭环检测四…...

C++项目集成Tesseract 5.x踩坑实录:从编译选项到内存管理的完整避坑指南

C项目集成Tesseract 5.x踩坑实录&#xff1a;从编译选项到内存管理的完整避坑指南 在计算机视觉和文档处理领域&#xff0c;Tesseract OCR引擎以其开源免费、多语言支持和较高的识别准确率&#xff0c;成为众多C项目的首选集成方案。然而&#xff0c;从源码编译到生产环境部署&…...

OpenClawBox:构建统一AI网关,实现多模型智能路由与成本优化

1. 项目概述&#xff1a;从零到一&#xff0c;打造你的个人AI路由中枢 如果你和我一样&#xff0c;在深度使用各类大语言模型&#xff08;LLM&#xff09;时&#xff0c;常常陷入一种甜蜜的烦恼&#xff1a;ChatGPT-4o的推理能力无与伦比&#xff0c;但价格不菲&#xff1b;Cl…...

用LangChain Tools打造会自主查资料的GPT模型

1. 项目概述&#xff1a;为什么你需要一个“会自己查资料”的GPT模型&#xff1f;我第一次在ChatGPT里输入“2024年巴黎奥运会新增了哪些比赛项目&#xff1f;”时&#xff0c;得到的回复是&#xff1a;“我的训练数据截止于2021年9月&#xff0c;无法提供2024年的最新信息。”…...

如何用dnGrep进行代码搜索:程序员必备的10个搜索模式

如何用dnGrep进行代码搜索&#xff1a;程序员必备的10个搜索模式 【免费下载链接】dnGrep Graphical GREP tool for Windows 项目地址: https://gitcode.com/gh_mirrors/dn/dnGrep dnGrep是一款强大的Windows图形化GREP搜索工具&#xff0c;专为开发者和技术用户设计。这…...

MyBatis 二级缓存脏读真实原因

很多同学熟悉 MyBatis 一级缓存、二级缓存基础用法&#xff0c;但多表联查、跨Mapper更新场景下的缓存脏读漏洞&#xff0c;90%的人都会踩坑。 本文结合完整实战案例&#xff0c;用大白话拆解&#xff1a;脏读如何产生、一级缓存二级缓存双重隐患、Namespace隔离缺陷&#xff0…...