蓝桥杯每日真题 - 第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 查找最接近的数值,从而找到两个不重叠子数组和之间的最小差值。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

大语言模型:解锁自然语言处理的无限可能

0.引言 在当今的科技时代&#xff0c;自然语言处理技术正以前所未有的速度发展&#xff0c;语言大模型作为其中的核心力量&#xff0c;对各个领域产生了深远的影响。本文旨在探讨语言大模型的发展历程、核心技术以及广泛的应用场景&#xff0c;以帮助读者更好地理解这一前沿技…

【vue2.0入门】vue基本语法

目录 引言一、页面动态插值1. 一般用法 二、计算属性computed三、动态class、style绑定四、条件渲染与列表渲染五、事件处理六、表单输入绑定七、总结 引言 本系列教程旨在帮助一些零基础的玩家快速上手前端开发。基于我自学的经验会删减部分使用频率不高的内容&#xff0c;并不…

【STM32F1】——无线收发模块RF200与串口通信

【STM32F1】——无线收发模块RF200与串口通信 一、简介 本篇主要对调试无线收发模块RF200的过程进行总结&#xff0c;实现了以下功能。 串口普通收发&#xff1a;使用STM32F103C8T6的USART2串口接收中断&#xff0c;实现两个无线收发模块RF200间的通信。 二、RF200介绍 电压…

《TCP/IP网络编程》学习笔记 | Chapter 8:域名及网络地址

《TCP/IP网络编程》学习笔记 | Chapter 8&#xff1a;域名及网络地址 《TCP/IP网络编程》学习笔记 | Chapter 8&#xff1a;域名及网络地址域名系统什么是域名&#xff1f;DNS 服务器IP 地址和域名之间的转换使用域名的必要性利用域名获取 IP 地址利用 IP 地址获取域名 基于 Wi…

前端开发中常用的包管理器(npm、yarn、pnpm、bower、parcel)

文章目录 1. npm (Node Package Manager)2. Yarn (Yarn Package Manager)3. pnpm4. Bower5. Parcel总结 前端开发中常用的包管理器主要有以下几个&#xff1a; 1. npm (Node Package Manager) 简介&#xff1a; npm 是 Node.js 的默认包管理器&#xff0c;也是最广泛使用的包…

HarmonyOS 如何实现传输中的数据加密

文章目录 摘要引言数据传输加密概述选择加密算法和传输协议加密实现方案与 Demo 代码配置 HTTPS/TLSAES 加密的实现代码详解RSA加密的实现代码详解 QA环节总结参考资料 摘要 本文将介绍在 HarmonyOS 应用中如何实现数据传输的加密策略。我们将讨论常见的加密算法&#xff08;如…

ArkTs简单入门案例:简单的图片切换应用界面

在鸿蒙 OS 应用开发的过程中&#xff0c;我们常常需要通过组合各种组件和编写相应的逻辑来实现丰富多样的功能。今天&#xff0c;我就来和大家详细解析一段实现简单图片切换功能的代码&#xff0c;希望能帮助到那些刚接触鸿蒙 OS 应用开发的朋友们。 一、代码导入部分 Entry …

influxDB 时序数据库安装 flux语法 restful接口 nodjsAPI

安装 Install InfluxDB | InfluxDB OSS v2 Documentation Debian和Ubuntu用户可以用apt-get包管理来安装最新版本的InfluxDB。 对于Ubuntu用户&#xff0c;可以用下面的命令添加InfluxDB的仓库&#xff0c;添加之后即可apt-get 安装influxdb2 wget -q https://repos.influx…

丹摩征文活动|丹摩智算平台使用指南

目录 1. 登录平台与工作环境设置1.1 访问与登录1.2 创建或选择项目1.3 初始化项目环境 2. 数据上传与管理2.1 数据上传2.2 数据管理与预处理2.3 数据可视化 3. 模型构建与训练3.1 模型选择3.2 参数配置3.3 模型训练与评估 4. 模型部署与应用4.1 模型部署4.2 接口调用与集成4.3 …

NAT网络工作原理和NAT类型

NAT基本工作流程 通常情况下&#xff0c;某个局域网中&#xff0c;只有路由器的ip是公网的&#xff0c;局域网中的设备都是内网ip&#xff0c;内网ip不具备直接与外部应用通信的能力。 处于内网的设备如何借助NAT来实现访问外网的应用&#xff1f; 对于开启了NAT功能的局域网…

LLMs 如何处理相互矛盾的指令?指令遵循优先级实验

编者按&#xff1a;想象一下&#xff0c;你正在开发一个 AI 助手&#xff0c;突然发现 system message 和用户提示词存在冲突&#xff0c;这时 AI 会听谁的&#xff1f;这种情况不仅困扰着开发者&#xff0c;还可能导致 AI 系统的不稳定和不可预测&#xff0c;影响用户体验和系…

qt QProcess详解

1、概述 QProcess是Qt框架提供的一个类&#xff0c;它用于在应用程序中执行外部进程。QProcess提供了一系列函数来启动、控制和与外部进程进行交互&#xff0c;使得开发者能够在自己的应用程序中集成和调用其他程序或服务。这个类在需要执行系统命令、启动其他应用程序或进行文…

Appium配置2024.11.12

百度得知&#xff1a;谷歌从安卓9之后不再提供真机layout inspector查看&#xff0c;仅用于支持ide编写的app调试用 所以最新版android studio的android sdk目录下已经没有了布局查看工具... windows x64操作系统 小米k30 pro手机 安卓手机 Android 12 第一步&#xff1a…

《ElementPlus 与 ElementUI 差异集合》Icon 图标 More 差异说明

参考 《element plus 使用 icon 图标(两种方式)》使用 icon 升级 Vue2 升级 Vue3 项目时&#xff0c;遇到命名时的实心与空心点差异&#xff01; ElementUI&#xff1a; 实心是 el-icon-more空心是 el-icon-more-outline ElementPlus&#xff1a; 实心是 el-icon-more-fill…

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

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

【数据结构与算法】第11课—数据结构之选择排序和交换排序

文章目录 1. 选择排序1.1 直接选择排序1.2 堆排序 2. 交换排序2.1 冒泡排序2.2 快速排序(找基准值法1----Hoare版本)2.2.1 特殊场景12.2.2 特殊场景22.2.3 代码2.2.4 快速排序的时间复杂度 2.3 快速排序(找基准值法2---挖坑法)2.3.1 特殊情况1处理2.3.2 特殊情况2处理 2.4 快速…

MySQL技巧之跨服务器数据查询:进阶篇-从A数据库复制到B数据库的表中

MySQL技巧之跨服务器数据查询&#xff1a;进阶篇-从A数据库复制到B数据库的表中 基础篇已经描述&#xff1a;借用微软的SQL Server ODBC 即可实现MySQL跨服务器间的数据查询。 而且还介绍了如何获得一个在MS SQL Server 可以连接指定实例的MySQL数据库的连接名: MY_ODBC_MYSQ…

UVC 输出视频格式修改和windows下数据分析

文章目录 前言一、UVC MJPEG视频帧描述符1.MJPG视频帧格式示例 二、UVC YUV2、NV12、M420、I420无压缩视频帧描述符GUID1.如YUV2数据参数初始为: 三、UVC Windows下UVC摄像头数据分析总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 项目需要&#…

大数据开发面试宝典

312个问题&#xff0c;问题涵盖广、从自我介绍到大厂实战、19大主题&#xff0c;一网打尽、真正提高面试成功率 一、Linux 1. 说⼀下linux的常⽤命令&#xff1f; 说一些高级命令即可 systemctl 设置系统参数 如&#xff1a;systemctl stop firewalld关闭防火墙 tail / hea…

更改Ubuntu22.04锁屏壁纸

更改Ubuntu22.04锁屏壁纸 sudo apt install gnome-shell-extensions gnome-shell-extension-manager安装Gnome Shell 扩展管理器后&#xff0c;打开“扩展管理器”并使用搜索栏找到“锁屏背景”扩展