蓝桥杯每日真题 - 第7天

题目:(爬山)

题目描述(X届 C&C++ B组X题)

解题思路:

  • 前缀和构造:为了高效地计算子数组的和,我们可以先构造前缀和数组 a,其中 a[i] 表示从第 1 个元素到第 i 个元素的和。这样,对于任意区间 [i, j] 的子数组和,可以通过 a[j] - a[i-1] 快速得到。

  • 枚举所有区间和:用双重循环枚举所有可能的区间 [i, j],将每个区间和存入 multiset s 中。multiset 支持快速查找、插入和删除,且自动排序,是处理该问题的合适选择。

  • 最小差值的计算

    • 遍历每一个位置 i,将该位置作为第一个区间的右端点。

    • multiset 中删除以 i 作为右端点的所有区间和,以避免区间重叠。

    • 然后遍历每一个可能的左端点 j,计算第一个区间 [j, i] 的和 k = a[i] - a[j-1]

    • 使用 lower_bound 查找 s 中最接近 k 的区间和,计算绝对差值,并更新最小差值 res

    • lower_bound 查找时,考虑 s 中前后两个元素,以确保找到最接近 k 的数值。

  • 输出结果:最终输出最小的差值 res

代码实现(C++):

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+10;
long long a[N];
int n;
multiset<long long>s;
long long minn(long long a,long long b){
    if(a<b) return a;
    else return b;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);//取消同步流
    cin>>n;
    for(int i = 1;i<=n;i++) {
        cin>>a[i];
        a[i]+=a[i-1];//构造前缀和
    }
    for(int i = 1;i<=n;i++){
        for(int j = i;j<=n;j++){
            s.insert(a[j]-a[i-1]);//枚举右区间所有情况先加入set中
        }
    }
    long long res = 1e9;
    //这里的i是第一个区间的右端点
    for(int i = 1;i<n;i++){
        //删除掉以i作为右区间第一个数字的情况
        for(int j = i;j<=n;j++){
//             auto p = s.find(a[j]-a[i-1]);
//             s.erase(p);
               auto k = a[j] - a[i-1];
                s.erase(s.find(k));
        }

        //这里的j是第一个区间的左端点
        for(int j = 1;j<=i;j++){
            auto k = a[i] - a[j-1];

            //找到又区间中最接近k的位置,用lower_bound(s.begin(),s.end(),k)
            //会慢很多,不建议
            auto p = s.lower_bound(k);
            if(p!=s.end()){
                res = minn(res,abs(*p-k));
            }
            if(p!=s.begin()){
                p--;
                res = minn(res,abs(*p-k));
                //lower_bound返回的是第一个>=k的数字,因此绝对值最小的情况也可能在p前面一点
            }
        }
    }
    cout<<res<<endl;
    return 0;
}

代码分析:

  • 头文件和常量定义

    • 引入头文件 #include <bits/stdc++.h>,方便使用标准库的各种数据结构和算法。

    • 定义常量 N 为数组的最大长度(设置为 1000)。

    • 定义数组 a[N] 用于存储前缀和,n 表示元素数量。

    • 使用 multiset s 存储所有子数组的和,支持排序和快速查找。

  • 辅助函数 minn

    • minn 函数用于返回两个数中的较小值,这个函数会在更新最小差值时使用。

    • 使用辅助函数代替 std::min 可以提高代码可读性。

  • 初始化和输入

    • ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); 是用于加快 I/O 操作的优化。

    • 读取输入 n 和数组元素,构造前缀和 a[i] += a[i - 1];a[i] 表示从第一个元素到第 i 个元素的和。

    • 构造前缀和后,可以通过 a[j] - a[i - 1] 快速获得区间 [i, j] 的和。

  • 枚举所有区间和并加入 multiset

    • 双重循环枚举所有可能的区间 [i, j]

    • 每个区间和通过 a[j] - a[i - 1] 计算,并插入 multiset s 中。

    • 使用 multiset 是因为它支持自动排序和快速查找最接近的值。

  • 枚举区间、删除重叠区间和查找最小差值

    • 外层循环的 i 表示第一个区间的右端点。

    • 内部循环先删除以 i 为右端点的所有区间和,避免第一个区间和第二个区间重叠。

    • 对于当前右端点 i,再枚举每个可能的左端点 j,计算第一个区间 [j, i] 的和 k = a[i] - a[j-1]

    • 使用 lower_bound 查找 s 中最接近 k 的值。由于 lower_bound 返回的是第一个大于等于 k 的迭代器 p,所以还需要检查 p 的前一个元素,以找到绝对差值最小的情况。

    • 最小差值存储在 res 中。

难度分析

⭐️⭐️⭐️⭐️ 

总结

  • 使用前缀和快速计算子数组和。

  • 使用 multiset 存储所有子数组和,以支持有序查找和删除操作。

  • 通过双重循环枚举区间和,并使用 lower_bound 查找最接近的数值,从而找到两个不重叠子数组和之间的最小差值。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Llama旋转位置编码代码实现及详解

旋转位置编码RoPE 在旋转位置编码与Transformer和BERT之间的区别中介绍了旋转位置编码&#xff08;RoPE&#xff09;的特点和优势&#xff0c;这种输入长度动态可变的优势使得在Llama编码时&#xff0c;不需要掩码将多余的嵌入掩住。为了详细了解RoPE是如何实现的&#xff0c;…

WebSocket和HTTP协议的性能比较与选择

WebSocket和HTTP协议的性能比较与选择 引言&#xff1a; 在web应用开发中&#xff0c;无论是实时聊天应用、多人在线游戏还是实时数据传输&#xff0c;网络连接的稳定性和传输效率都是关键要素之一。目前&#xff0c;WebSocket和HTTP是两种常用的网络传输协议&#xff0c;它们…

WebRTC项目一对一视频

开发步骤 1.客户端显示界面 2.打开摄像头并显示到页面 3.websocket连接 4.join、new-peer、resp-join信令实现 5.leave、peer-leave信令实现 6.offer、answer、candidate信令实现 7.综合调试和完善 1.客户端显示界面 步骤&#xff1a;创建html页面 主要是input、button、vide…

GIS基础知识:WKT格式、WKB格式

什么是WKT格式&#xff1f; WKT&#xff08;Well-Known Text&#xff09;是一种用于描述地理空间几何对象的文本格式。 这种格式是由Open Geospatial Consortium&#xff08;OGC&#xff09;定义并维护的一种开放标准&#xff0c;主要用于在不同的GIS系统和数据库之间交换空间…

力扣(LeetCode)611. 有效三角形的个数(Java)

White graces&#xff1a;个人主页 &#x1f649;专栏推荐:Java入门知识&#x1f649; &#x1f439;今日诗词:雾失楼台&#xff0c;月迷津渡&#x1f439; ⛳️点赞 ☀️收藏⭐️关注&#x1f4ac;卑微小博主&#x1f64f; ⛳️点赞 ☀️收藏⭐️关注&#x1f4ac;卑微小博主…

Mac Nginx 前端打包部署

安装homebrew /bin/zsh -c "$(curl -fsSL https://gitee.com/cunkai/HomebrewCN/raw/master/Homebrew.sh)" 安装Nginx brew install nginx nginx相关命令 nginx启动命令&#xff1a;nginx nginx -s reload #重新加载配置 nginx -s reopen #重启 nginx -s stop #…

利用VMware workstation pro 17安装 Centos7虚拟机以及修改网卡名称

通过百度网盘分享的文件&#xff1a;安装虚拟机必备软件 链接&#xff1a;https://pan.baidu.com/s/1rbYhDh8x1hTzlSNihm49EA?pwdomxy 提取码&#xff1a;omxy 123网盘 https://www.123865.com/s/eXPrVv-UsKch 提取码:eNcy 先自行安装好VMware workstation pro 17 设置虚拟机…

《实时流计算系统设计与实现》-Part 2-笔记

做不到实时 做不到实时的原因 实时计算很难。通过增量计算的方式来间接获得问题的&#xff08;伪&#xff09;实时结果&#xff0c;即使这些结果带有迟滞性和近似性&#xff0c;但只要能够带来尽可能最新的信息&#xff0c;那也是有价值的。 原因可分成3个方面&#xff1a; …

《C陷阱与缺陷》

文章目录 1、【词法陷阱】1.1 符号与组成符号间的关系1.1 与 1.3 y x/*p 与 y x/(*p)&#xff0c;a-1 与 a - 1 与 a -1, 老版本编译器的处理是不同的&#xff0c;严格的ANSI C则会报错1.4 十进制的 076&#xff0c;会被处理为八进制&#xff0c;ANSI C禁止这种用法&#x…

初阶C++之C++入门基础

大家好&#xff01;欢迎来到C篇学习&#xff0c;这篇文章的内容不会很难&#xff0c;为c的引入&#xff0c;c的重点内容将在第二篇的文章中讲解&#xff0c;届时难度会陡然上升&#xff0c;请做好准备&#xff01; 我们先看网络上的一个梗&#xff1a;21天内⾃学精通C 好了&am…

Maven 构建项目

Maven 是一个项目管理和构建工具&#xff0c;主要用于 Java 项目。它简化了项目的构建、依赖管理、报告生成、发布等一系列工作。 构建自动化&#xff1a;Maven 提供了一套标准化的构建生命周期&#xff0c;包括编译、测试、打包、部署等步骤&#xff0c;通过简单的命令就可以执…

Android中桌面小部件的开发流程及常见问题和解决方案

在Android中&#xff0c;桌面小部件&#xff08;App Widget&#xff09;是应用程序可以在主屏幕或其他地方显示的一个可视化组件&#xff0c;提供简化信息和交互功能。Android桌面小部件的framework为开发者提供了接口&#xff0c;使得可以创建和更新小部件的内容。以下是Andro…

opencv(c++)----图像的读取以及显示

opencv(c)----图像的读取以及显示 imread: 作用&#xff1a;读取图像文件并将其加载到 Mat 对象中。参数&#xff1a; 第一个参数是文件路径&#xff0c;可以是相对路径或绝对路径。第二个参数是读取标志&#xff0c;比如 IMREAD_COLOR 表示以彩色模式读取图像。 返回值&#x…

马斯克万卡集群AI数据中心引发的科技涟漪:智算数据中心挑战与机遇的全景洞察

一、AI 爆发重塑数据中心格局 随着AI 技术的迅猛发展&#xff0c;尤其是大模型的崛起&#xff0c;其对数据中心产生了极为深远的影响。大模型以其数以亿计甚至更多的参数和对海量数据的处理需求&#xff0c;成为了 AI 发展的核心驱动力之一&#xff0c;同时也为数据中心带来了…

搭建Python2和Python3虚拟环境

搭建Python3虚拟环境 1. 更新pip2. 搭建Python3虚拟环境第一步&#xff1a;安装python虚拟化工具第二步&#xff1a; 创建虚拟环境 3. 搭建Python2虚拟环境第一步&#xff1a;安装虚拟环境模块第二步&#xff1a;创建虚拟环境 4. workon命令管理虚拟机第一步&#xff1a;安装扩…

C语言的内存函数(文章后附gitee链接,模拟实现函数)

之前我们已经讲解过了字符型数据的一类字符串函数&#xff0c; 现在我们来讨论字符型以外的数据处理。 1&#xff1a;memcpy 的使用和模拟实现 void * memcpy ( void * destination, const void * source, size_t num )&#xff1b; 注意&#xff1a; 1&#xff1a;函数memcp…

FPGA/Verilog,Quartus环境下if-else语句和case语句RT视图对比/学习记录

基本概念 RTL&#xff08;Register - Transfer - Level&#xff09;视图&#xff1a;是一种硬件描述语言的抽象层次&#xff0c;用于描述数字电路中寄存器之间的数据传输和操作。在这个层次上&#xff0c;可以看到电路的基本结构&#xff0c;如寄存器、组合逻辑、多路复用器等…

react的创建与书写

一&#xff1a;创建项目 超全面详细一条龙教程&#xff01;从零搭建React项目全家桶&#xff08;上篇&#xff09; - 知乎 1.创建一个文件夹&#xff0c;shift鼠标右键选择在此处打开powershell 2.为了加速npm下载速度&#xff0c;先把npm设置为淘宝镜像地址。 npm config s…

【动态规划】两个数组的 dp 问题

1. 最长公共子序列 1143. 最长公共子序列 状态表示&#xff1a; dp[i][j] 表示 s1 的 0 ~ i 区间和 s2 的 0 ~ j 区间内所有子序列中&#xff0c;最长公共子序列的长度 状态转移方程&#xff1a; 当 s1[i] 和 s2[j] 相等时&#xff0c;那么最长公共子序列一定是以这两个位置…

【计算机网络】【传输层】【习题】

计算机网络-传输层-习题 文章目录 10. 图 5-29 给出了 TCP 连接建立的三次握手与连接释放的四次握手过程。根据 TCP 协议的工作原理&#xff0c;请填写图 5-29 中 ①~⑧ 位置的序号值。答案技巧 注&#xff1a;本文基于《计算机网络》&#xff08;第5版&#xff09;吴功宜、吴英…