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

蓝桥杯 区间移位--二分、枚举

题目

代码

#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;//更新kk可以到更远

                }

                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

错误的原因&#xff1a; 1、可能是你的网络DNS配置错误。 2、由request header过大所引起&#xff0c;request过大&#xff0c;通常是由于cookie中写入了较大的值所引起的。 3、访问太频繁&#xff0c;浏览器的缓存量太大&#xff0c;产生错误。 解决办法&#xff1a; 1、清…...

【Redis】一种常见的Redis分布式锁原理简述

本文主要简述一下基于set命令的Redis分布式锁的原理。 一&#xff0c;a线程持有的锁不要被b线程同时持有→setnx 抢锁的时候&#xff0c;最核心的就是&#xff0c;a线程持有的锁不要被b线程同时持有&#xff0c;放在基于set命令的redis分布式锁中来看&#xff0c;就是“如果锁…...

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是一款功能强大的磁盘分区工具&#xff0c;它支持Windows和Mac OS X系统&#xff0c;可以用于管理硬盘分区&#xff0c;包括扩容Mac OS X的Apple APFS分区。然而&#xff0c;直接使用DiskGenius来扩容Mac OS X的APFS分区可能存在一定的风险&#xff0c;因为不是专门为…...

从零开始的LeetCode刷题日记:70. 爬楼梯

一.相关链接 题目链接&#xff1a;70. 爬楼梯 二.心得体会 这道题还是动规五部曲。 1.首先是dp数组及其下标的含义&#xff0c;dp记录了每层楼梯对应的爬的方法&#xff0c;每个下标存储每个对应楼层。 2.然后是递归公式&#xff0c;其实每一层楼都是可以从下面一层和下面…...

Unity照片墙效果

Unity照片墙效果&#xff0c;如下效果展示 。 工程源码...

【自动化利器】12个评估大语言模型(LLM)质量的自动化框架

LLM评估是指在人工智能系统中评估和改进语言和语言模型的过程。在人工智能领域&#xff0c;特别是在自然语言处理&#xff08;NLP&#xff09;及相关领域&#xff0c;LLM评估具有至高无上的地位。通过评估语言生成和理解模型&#xff0c;LLM评估有助于细化人工智能驱动的语言相…...

【1】基础概念

文章目录 一、特点二、基础语法注意三、官方编程指南四、go 语言标准库 API 一、特点 golang 一个 go 文件都要归属到一个包&#xff0c;需要进行申明。天然的并发&#xff1a;golang 从语言层面支持大并发。每个 go 文件都必须要归属到一个包中。执行 go 文件&#xff1a;go …...

HTML 文档规范与解析模式:DOCTYPE、<html> 标签以及结构化页面

文章目录 `<!DOCTYPE html>` 文档类型声明标准模式与怪异模式HTML5 的简化声明`<html>` 标签`<head>` 标签`<body>` 标签小结<!DOCTYPE html> 文档类型声明 在 HTML 文档中,<!DOCTYPE html> 是一个重要的文档类型声明,主要用于告知浏览…...

大模型微调技术 --> 脉络

Step1:脉络 微调技术从最早期的全模型微调演变成如今的各种参数高效微调(PEFT)方法&#xff0c;背后是为了应对大模型中的计算、存储和数据适应性的挑战 1.为什么有微调&#xff1f; 深度学习模型越来越大&#xff0c;尤其是 NLP 中的预训练语言模型(BERT, GPT)系列。如果从…...

不要只知道deepl翻译,这里有10个专业好用的翻译工具等着你。

deepl翻译的优点还是有很多的&#xff0c;比如翻译的准确性很高&#xff0c;支持翻译的语言有很多&#xff0c;并且支持翻译文件和文本。但是现在翻译工具那么多&#xff0c;大家需要翻译的场景也有很多&#xff0c;怎么能只拥有一个翻译工具呢。所以在这里我帮助大家寻找了一波…...

第二节 管道符、重定向与环境变量

1.重定向技术的 5 种模式 &#xff08;1&#xff09;标准覆盖输出重定向 &#xff08;2&#xff09;标准追加输出重定向 &#xff08;3&#xff09;错误覆盖输出重定向 &#xff08;4&#xff09;错误追加输出重定向 &#xff08;5&#xff09;输入重定向2.输入输出重定向 输入…...

Linux 服务器使用指南:从入门到登录

&#x1f31f;快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。 &#x1f31f; &#x1f6a9;博主致力于用通俗易懂且不失专业性的文字&#xff0c;讲解计算机领域那些看似枯燥的知识点&#x1f6a9; 目录 一…...

QT 如何使QLabel的文字垂直显示

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

蓬勃发展:移动开发——关于软件开发你需要知道些什么

一、前言 移动开发一直都是软件开发领域中最有趣的领域之一&#xff0c;这是因为&#xff1a; 1、移动开发为“只有一个人”的开发团队提供了一个非常独特的机会&#xff0c;让他可以在相对较短的时间内建立一个实际的、可用的、有意义的应用程序&#xff1b; 2、移动开发也代…...

1095. 山脉数组中查找目标值

目录 题目解法lambda在这是怎么用的&#xff1f; 题目 &#xff08;这是一个 交互式问题 &#xff09; 你可以将一个数组 arr 称为 山脉数组 当且仅当&#xff1a; arr.length > 3 存在一些 0 < i < arr.length - 1 的 i 使得&#xff1a; arr[0] < arr[1] <…...

【深度学习】InstantIR:图片高清化修复

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

推荐一款PowerPoint转Flash工具:iSpring Suite

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

如何搭建汽车行业AI知识库:定义+好处+方法步骤

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

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)

macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 &#x1f37a; 最新版brew安装慢到怀疑人生&#xff1f;别怕&#xff0c;教你轻松起飞&#xff01; 最近Homebrew更新至最新版&#xff0c;每次执行 brew 命令时都会自动从官方地址 https://formulae.…...