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

news/2024/11/8 7:43:01/

题目

代码

#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.ppmy.cn/news/1545294.html

相关文章

Ubuntu 安装Nvidia 显卡驱动

在Nvidia官网下载对应驱动&#xff1a;https://www.nvidia.cn/geforce/drivers/ sudo vim /etc/modprobe.d/blacklist.confblacklist vga16fbblacklist nouveaublacklist rivafbblacklist rivatvblacklist nvidiafboptions nouveau modeset0 sudo update-initramfs -u sudo re…

Swift 扩展

Swift 扩展 Swift 是一种强大的编程语言,由苹果公司开发,用于iOS、macOS、watchOS和tvOS应用程序的开发。自2014年发布以来,Swift因其易于阅读和编写的语法、现代化的设计以及出色的性能而广受欢迎。本文将探讨Swift的一些关键特性,并讨论其在软件开发领域的应用和未来发展…

IntersectionObserver鼠标在页面左右滑动时,右侧滚动条会上下抖动,但页面不会

这通常是由于页面宽度设置不当导致的。当页面内容没有占满屏幕时&#xff0c;右侧不会出现滚动条&#xff0c;但当内容加载更多时&#xff0c;页面宽度设置为auto会导致整个页面向左移动&#xff0c;从而产生抖动现象。 解决方法 设置页面宽度为100vw‌&#xff1a;通过设置b…

Meta AI最新推出的长视频语言理解多模态模型LongVU分享

LongVU是由Meta AI团队推出的一种专注于长视频语言理解的多模态模型。 LongVU的架构设计包括使用DINOv2技术去除冗余帧&#xff0c;融合剩余帧的特征&#xff0c;通过跨模态查询选择性地减少视觉标记&#xff0c;根据时间依赖关系进行空间标记压缩&#xff0c;以进一步适应大型…

代码随想录之字符串刷题总结

目录 1.反转字符串 2.反转字符串II 3.替换数字 4.翻转字符串里面的单词 5.右旋&&左旋字符串 1.反转字符串 题目描述&#xff1a; 编写一个函数&#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外…

【信号处理】基于联合图像表示的深度学习卷积神经网络

Combined Signal Representations for Modulation Classification Using Deep Learning: Ambiguity Function, Constellation Diagram, and Eye Diagram 信号表示 Ambiguity Function(AF) 模糊函数描述了信号的两个维度(dimensions):延迟(delay)和多普勒(Doppler)。 …

【设计模式系列】总览

努力填完如下表格ing... 设计模式简述详细链接单例模式&#xff08;Singleton&#xff09;工厂方法模式&#xff08;Factory Method&#xff09;简单工厂模式&#xff08;Simple Factory Pattern&#xff09;简单工厂模式是一个静态的工厂类&#xff0c;它提供一个根据参数决定…

反转链表(Leetcode)

反转链表 Leetcode题目链接 题意&#xff1a;翻转一个单链表 &#x1f330;: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 在链表本身进行反转即可&#xff0c;不用重新定义链表&#xff0c;这同时浪费时间和空间。 需要采用哑…