蓝桥杯 区间移位--二分、枚举
题目
代码
#include <stdio.h> #include <string.h> #include <vector> #include <algorithm> #include <iostream> using namespace std; struct node{ int a,b; }; vector<node> q; bool cmp(node x,node y){ return x.b < y.b; } bool check(int m){ //最大的移动距离m,判断移动完之后能否覆盖整个区间 vector<node> tmp(q);//复制一个vector q int k=0;//能覆盖的右端点 while(true){ bool flag=false; for(int i=0;i<tmp.size();i++){//对每个区间都移动一下 node now=tmp[i];
int ta=now.a; int tb=now.b; //k应该在【ta-m , tb+m】 里才能保持连接的10000长度 //下面讨论的是如果在 if(ta-m <= k && tb+m >= k){ // 如果当前区间的移动后能与 k 连接,则更新 k 的值。 flag=true; int len=tb-ta;//当前区间的长度
if(ta+m >= k){ k=k+len;//更新k,k可以到更远 } else{ k=tb+m; } tmp.erase(tmp.begin()+i); break; } } if(k >= 20000 || !flag)//如果没有区间符合 break; } return k >= 20000;//当前假设长度m符合最终条件,可以考虑调小 } int main(){ int n; cin>>n; for(int i=0;i<n;i++){ int aa,bb; cin>>aa>>bb; //因为最后答案可能存在0.5,所以扩大两倍 //最后再除以2 aa = aa*2; bb = bb*2; q.push_back({aa,bb}); } //对vector排序 sort(q.begin(),q.end(),cmp); int l=0,r=20000;//区间 while(l<=r){ int mid=(l+r)/2; if(check(mid)){//如果能满足最终条件,说明该mid偏大,答案在左半段, //找最小的左端点 r=mid-1; } else l=mid+1; } //最后l=r //cout<<l<<' '<<r<<endl; double ans=l/2.0;//最后有0.5 cout<<ans<<endl; return 0; } |
运行评判结果
总结:
每个区间的两个端点分别为 a 和 b,要求找到一个最小的移动距离 m,使得所有区间通过向左或向右移动不超过 m 的距离后能够连续覆盖 [0, 10000] 这个区间。由于答案可能包含 0.5,所以将输入的区间扩大了两倍来处理,最终结果再除以2。使用二分查找来确定最小的移动距离 m。首先定义搜索的上下界,然后不断缩小范围直到找到满足条件的最小 m 值。使用变量 k 来追踪当前已覆盖的最右端点。如果当前区间的移动后能与 k 连接,则更新 k 的值。
相关文章:

蓝桥杯 区间移位--二分、枚举
题目 代码 #include <stdio.h> #include <string.h> #include <vector> #include <algorithm> #include <iostream> using namespace std; struct node{ int a,b; }; vector<node> q; bool cmp(node x,node y){ return x.b <…...
Nginx 报错400 Request Header Or Cookie Too Large
错误的原因: 1、可能是你的网络DNS配置错误。 2、由request header过大所引起,request过大,通常是由于cookie中写入了较大的值所引起的。 3、访问太频繁,浏览器的缓存量太大,产生错误。 解决办法: 1、清…...
【Redis】一种常见的Redis分布式锁原理简述
本文主要简述一下基于set命令的Redis分布式锁的原理。 一,a线程持有的锁不要被b线程同时持有→setnx 抢锁的时候,最核心的就是,a线程持有的锁不要被b线程同时持有,放在基于set命令的redis分布式锁中来看,就是“如果锁…...

HOT100_最大子数组和
class Solution {public int maxSubArray(int[] nums) {int[] dp new int[nums.length];int res nums[0];dp[0] nums[0];for(int i 1; i< nums.length; i){dp[i] Math.max(nums[i] ,dp[i-1] nums[i]);res Math.max(res, dp[i]);}return res;} }...
DiskGenius工具扩容Mac OS X Apple APFS分区
DiskGenius是一款功能强大的磁盘分区工具,它支持Windows和Mac OS X系统,可以用于管理硬盘分区,包括扩容Mac OS X的Apple APFS分区。然而,直接使用DiskGenius来扩容Mac OS X的APFS分区可能存在一定的风险,因为不是专门为…...
从零开始的LeetCode刷题日记:70. 爬楼梯
一.相关链接 题目链接:70. 爬楼梯 二.心得体会 这道题还是动规五部曲。 1.首先是dp数组及其下标的含义,dp记录了每层楼梯对应的爬的方法,每个下标存储每个对应楼层。 2.然后是递归公式,其实每一层楼都是可以从下面一层和下面…...

Unity照片墙效果
Unity照片墙效果,如下效果展示 。 工程源码...

【自动化利器】12个评估大语言模型(LLM)质量的自动化框架
LLM评估是指在人工智能系统中评估和改进语言和语言模型的过程。在人工智能领域,特别是在自然语言处理(NLP)及相关领域,LLM评估具有至高无上的地位。通过评估语言生成和理解模型,LLM评估有助于细化人工智能驱动的语言相…...
【1】基础概念
文章目录 一、特点二、基础语法注意三、官方编程指南四、go 语言标准库 API 一、特点 golang 一个 go 文件都要归属到一个包,需要进行申明。天然的并发:golang 从语言层面支持大并发。每个 go 文件都必须要归属到一个包中。执行 go 文件:go …...

HTML 文档规范与解析模式:DOCTYPE、<html> 标签以及结构化页面
文章目录 `<!DOCTYPE html>` 文档类型声明标准模式与怪异模式HTML5 的简化声明`<html>` 标签`<head>` 标签`<body>` 标签小结<!DOCTYPE html> 文档类型声明 在 HTML 文档中,<!DOCTYPE html> 是一个重要的文档类型声明,主要用于告知浏览…...
大模型微调技术 --> 脉络
Step1:脉络 微调技术从最早期的全模型微调演变成如今的各种参数高效微调(PEFT)方法,背后是为了应对大模型中的计算、存储和数据适应性的挑战 1.为什么有微调? 深度学习模型越来越大,尤其是 NLP 中的预训练语言模型(BERT, GPT)系列。如果从…...

不要只知道deepl翻译,这里有10个专业好用的翻译工具等着你。
deepl翻译的优点还是有很多的,比如翻译的准确性很高,支持翻译的语言有很多,并且支持翻译文件和文本。但是现在翻译工具那么多,大家需要翻译的场景也有很多,怎么能只拥有一个翻译工具呢。所以在这里我帮助大家寻找了一波…...

第二节 管道符、重定向与环境变量
1.重定向技术的 5 种模式 (1)标准覆盖输出重定向 (2)标准追加输出重定向 (3)错误覆盖输出重定向 (4)错误追加输出重定向 (5)输入重定向2.输入输出重定向 输入…...

Linux 服务器使用指南:从入门到登录
🌟快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。 🌟 🚩博主致力于用通俗易懂且不失专业性的文字,讲解计算机领域那些看似枯燥的知识点🚩 目录 一…...

QT 如何使QLabel的文字垂直显示
想要实现QLabel文字的垂直显示,可以通过使用“文字分割填充换行符”的方式来实现QLabel文字垂直显示的效果,下面是效果图: 具体实现代码: #include "mainwindow.h" #include "ui_mainwindow.h"MainWindow:…...

蓬勃发展:移动开发——关于软件开发你需要知道些什么
一、前言 移动开发一直都是软件开发领域中最有趣的领域之一,这是因为: 1、移动开发为“只有一个人”的开发团队提供了一个非常独特的机会,让他可以在相对较短的时间内建立一个实际的、可用的、有意义的应用程序; 2、移动开发也代…...
1095. 山脉数组中查找目标值
目录 题目解法lambda在这是怎么用的? 题目 (这是一个 交互式问题 ) 你可以将一个数组 arr 称为 山脉数组 当且仅当: arr.length > 3 存在一些 0 < i < arr.length - 1 的 i 使得: arr[0] < arr[1] <…...

【深度学习】InstantIR:图片高清化修复
InstantIR——借助即时生成参考的盲图像修复新方法 作者:Jen-Yuan Huang 等 近年来,随着深度学习和计算机视觉技术的飞速发展,图像修复技术取得了令人瞩目的进步。然而,对于未知或复杂退化的图像进行修复,仍然是一个充满挑战的任务。针对这一难题,研究者们提出了 Insta…...

推荐一款PowerPoint转Flash工具:iSpring Suite
iSpring Suite是一款PowerPoint转Flash工具,使用iSpring Suite 8可以轻松的将PPT演示文档转换为对Web友好的Flash影片格式。软件界面简洁,使用方便。为什么要转换成flash格式呢?Flash格式的最大特点是体积小巧、易于分发,兼容所有的操作系统…...

如何搭建汽车行业AI知识库:定义+好处+方法步骤
在汽车行业,大型车企面临着员工众多、价值链长、技术密集和知识传播难等挑战。如何通过有效的知识沉淀与应用,提升各部门协同效率,快速响应客户咨询,降低销售成本,并开启体系化、可持续性的知识管理建设,成…...

【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...

基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...

2025盘古石杯决赛【手机取证】
前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来,实在找不到,希望有大佬教一下我。 还有就会议时间,我感觉不是图片时间,因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...

MySQL 知识小结(一)
一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库,分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷,但是文件存放起来数据比较冗余,用二进制能够更好管理咱们M…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...

数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...