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

题目

代码

#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 的值。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/2324.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

华为ENSP--ISIS路由协议

项目背景 为了确保资源共享、办公自动化和节省人力成本&#xff0c;公司E申请两条专线将深圳总部和广州、北京两家分公司网络连接起来。公司原来运行OSFP路由协议&#xff0c;现打算迁移到IS-IS路由协议&#xff0c;张同学正在该公司实习&#xff0c;为了提高实际工作的准确性和…

Java-I/O框架10:File类、文件操作

视频链接&#xff1a;16.26 文件操作_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1Tz4y1X7H7?spm_id_from333.788.videopod.episodes&vd_sourceb5775c3a4ea16a5306db9c7c1c1486b5&p26 1.File类概述 概念&#xff1a;代表物理盘符中的一个文件或者文件夹&am…

设计模式之模块方法

定义 模板与方法应该是最常使用的设计模式&#xff0c;在GOF&#xff08;设计模式&#xff09;中的定义&#xff1a;定义一个操作中的算法的骨架 &#xff0c;而将一些步骤延迟到子类中。 Template Method使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。 …

【面试经典150】day 10

目录 1.验证回文串 2.判断子序列 3.两数之和 II - 输入有序数组 4.盛最多水的容器 5.三数之和 1.验证回文串 class Solution {public boolean isPalindrome(String s) {int i0,js.length()-1;while(i<j){//跳过非数字/字母while(i<j&&!Character.isLetterOrDig…

《双指针篇》---有效三角形的个数(中等)

题目传送门 方法一&#xff1a;排序双指针 1.排序 2.设置一个for循环。用来当做第三边。我们从后往前遍历。直到 i2 时跳出循环。 3.初始化 left 指针0&#xff0c;初始化right 指针等于 i-1。这样我们判断两边之和。 4.在left < right 的情况了&#xff0c;如果两边之和大…

Vue 权限管理

vue 中&#xff0c;比较常见的需要进行权限管控的权限控制实现思路有四条&#xff1a;、 菜单的控制 在登录请求中&#xff0c;会得到权限数据&#xff0c;当然&#xff0c;这个需要后端返回数据的支持&#xff0c;前端根据权限数据&#xff0c;展示对应的菜单&#xff0c;单…

结合自身的实际情况,试描绘一天的活动

结合自身的实际情况&#xff0c;试描绘一天的活动 现在变成了两眼一睁就是看看hcy和sxh发围脖了没

【力扣打卡系列】反转链表

坚持按题型打卡&刷&梳理力扣算法题系列&#xff0c;语言为go&#xff0c;Day12 反转链表 题目描述 解题思路 最开始的头节点为空&#xff0c;可以赋值为nil从前往后依次逆转下一个节点的指向即可 代码参考 /*** Definition for singly-linked list.* type ListNode s…

Spring Boot——配置文件

1. 配置文件的格式 Spring Boot 的配置文件有以下三种&#xff1a; application.propertiesapplication.ymlapplication.yaml yml 是 yaml 的简写&#xff0c;使用方法是一样的 当应用程序启动时&#xff0c;Spring Boot 会自动从 classpath 路径找到并加载 application.prop…

申请CNAS软件测试资质,如何选择测试工具最具性价比?

CNAS官方认可文件中对软件测试实验室需要配备的软件测试设备有如下要求&#xff1a; 1、软件测试设备可包括测试工具软件以及计算机系统、网络系统、适配器、测试输入和结果输出等硬件设备。当利用计算机或自动设备对软件测试数据进行采集、处理、记录、报告、存储或检索时&am…

ssm048电子竞技管理平台的设计与实现+jsp(论文+源码)_kaic

毕 业 设 计&#xff08;论 文&#xff09; 题目&#xff1a;电子竞技管理平台设计与实现 摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本电子竞技管理平台…

Android启动流程_Init阶段

前言 本文将会介绍 Android 启动流程&#xff0c;将基于 Android 10 代码逻辑介绍原生启动过程。 bootloader 上电 -> 加载 recovery 镜像或者 boot 镜像 -> linux kernel 启动 -> 加载 init 进程 -> 加载 zygote 进程 -> systemserver 进程 -> 系统启动 …

国标GB28181网页直播平台EasyGBS国标GB28181软件的应急管理与安全生产解决方案

在当今社会&#xff0c;安全生产和应急管理已经成为各行各业不可或缺的重要部分。全面提高安全生产管理水平、构建责任全覆盖、监管全过程、监管全方位的综合治理体系已成为社会发展的必然趋势。国标GB28181网页直播平台EasyGBS作为一款基于国标GB28181协议的视频融合管理平台&…

Python | Leetcode Python题解之第523题连续的子数组和

题目&#xff1a; 题解&#xff1a; class Solution:def checkSubarraySum(self, nums, k):d {0: -1}pre 0for index, num in enumerate(nums):pre numrem pre % ki d.get(rem, index)if i index:d[rem] indexelif i < index - 2:return Truereturn False

C++练习题

//C输出 "Hello, World!" #include <iostream> using namespace std; int main() { //printf("Hello World!"); cout<<"Hello World!"<<endl; return 0; } //C输出整数 #include <iostream> using names…

ChatGPT「AI搜索」正式上线:AI搜索要变天了?「速看体验与对比」

随着人工智能的发展&#xff0c;传统搜索引擎难以满足用户日益复杂的信息需求&#xff0c;AI搜索工具就因此诞生。10月31日&#xff0c;OpenAI发布了新的「ChatGPT Search」功能&#xff0c;为其智能聊天系统引入了实时网络搜索。借助这一功能&#xff0c;ChatGPT可以通过自然的…

Docker安装MySQL8.0

文章目录 1、通过Docker运行msyql82、进入容器配置mysql远程连接3、通过Navicat远程访问mysql 1、通过Docker运行msyql8 mkdir -p /home/mysql8/data /home/mysql8/config /home/mysql8/logsdocker run -d \ --name mysql8 \ --privilegedtrue \ --restartalways \ -p 3310…

JAVA基础:数据类型与运算符 (习题笔记)

1.输入自己的名字&#xff0c;年龄和性别&#xff0c;分别用不同的变量接收&#xff0c;并将输入的信息做输出。 public static void main(String[] args) {Scanner input new Scanner(System.in);System.out.println("请输入你的名字&#xff1a;");String name i…

Windows 笔记本WiFi 功能消失解决办法

Windows 笔记本用户在使用 WiFi 时遇到功能突然消失的问题确实比较常见。这通常不是病毒造成的&#xff0c;而是其他几个常见原因所导致的。以下是一些可能的原因及解决方案&#xff1a; 视频教程【win10系统无网络&#xff0c;无wifi解决办法】 https://www.bilibili.com/vid…

opencv学习笔记(6):图像预处理(直方图、图像去噪)

3.直方图 直方图是用来表现图像中亮度分布的&#xff0c;给出的是图像中某个亮度或者某个范围亮度下共有几个像素&#xff0c;即统计一幅图某个亮度像素的数量。 直方图不能反映某一灰度值像素在图像中的位置&#xff0c;失去了图像的空间信息。图像直方图由于其计算代价较小&a…