蓝桥杯每日真题 - 第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.xdnf.cn/news/14888.html

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

相关文章

socketcan-goloang

模拟接收 模拟发送 package mainimport ("context""fmt""go.einride.tech/can""go.einride.tech/can/pkg/candevice""go.einride.tech/can/pkg/socketcan" )func main() {// linux系统设置// sudo ip link add dev can0 ty…

Java期末复习暨学校第五次上机课作业

Java期末复习暨学校第五次上机课作业&#xff1a;掌握类的定义、掌握类的封装、熟悉类的成员方法的调用。 第一题&#xff1a; 先定义两个整形变量x和y&#xff0c;然后showMessage方法打印防御塔的位置。 然后通过new关键字实例化了一个TowerDefense对象t1,并把x赋值为3&…

【目标检测】【Ultralytics-YOLO系列】Windows11下YOLOV5人脸目标检测

【目标检测】【Ultralytics-YOLO系列】Windows11下YOLOV5人脸目标检测 文章目录 【目标检测】【Ultralytics-YOLO系列】Windows11下YOLOV5人脸目标检测前言YOLOV5模型运行环境搭建YOLOV5模型运行数据集准备YOLOV5运行模型训练模型验证模型推理 总结 前言 Ultralytics YOLO 是一…

【启明智显分享】5G CPE与5G路由器到底有什么区别?

5G路由器和5G CPE在功能和应用场景上存在很明显的差异&#xff0c;小编做了详细比较&#xff0c;希望能帮助到你进一步了解他们的区别及应用。 一、定义与功能 5G路由器 5G路由器是一个将5G网络连接转换为Wi-Fi信号的设备&#xff0c;使多个Wi-Fi设备可以通过5G网络进行连接…

【go从零单排】File Paths文件路径

&#x1f308;Don’t worry , just coding! 内耗与overthinking只会削弱你的精力&#xff0c;虚度你的光阴&#xff0c;每天迈出一小步&#xff0c;回头时发现已经走了很远。 &#x1f4d7;概念 在 Go 中&#xff0c;处理文件路径通常使用 path/filepath 包。这个包提供了一系…

【数据分享】中国渔业统计年鉴(1979-2024) pdf

数据介绍 一、《中国渔业统计年鉴》以正式出版年份标序。其统计数据起讫日期:渔民家庭收支调查起讫时间为 2022年11月1日至2023年10月31日&#xff0c;其他数据起讫时间为2023年1月1日至2023年12月31日。 二、统计数据中&#xff0c;远洋渔业数据按照远洋渔业管理办法进行统计…

Windows10“大限”将至或加速政企信创进程

近日&#xff0c;微软公司正式宣布将于2025年10月14日终止对Windows 10系统的支持服务。Windows 10“退休”在即&#xff0c;信息安全风险陡增——对此&#xff0c;360织语的安全专家认为&#xff0c;对于政企用户而言&#xff0c;不管是选择继续使用Windows 10&#xff0c;还是…

文本嵌入方案大总结:从词向量到句向量

这里写目录标题 文本嵌入方案总结一、文本嵌入三种层次 词向量应用&#xff1a; 句向量应用&#xff1a; 扩展&#xff1a;文本嵌入和句子相似度、文本匹配的逻辑关系&#xff1f; 二、词向量有哪些方案、优缺点、工具&#xff1f;方案一&#xff1a;统计编码方案二&…

第23天Linux下常用工具(二)

目录 第四章 GDB调试工具 4.1gdb的作用 4.2调试代码的流程 4.3gdb的安装 4.4 gdb的使用 第五章 makefile工程管理工具 5.1makefile的作用 5.2makefile的运行 5.3make的安装 5.4makefile的编写方法 5.5makefile的语法 5.6makefile使用示例 第四章 GDB调试工具 4.1g…

ubuntu22.04与ubuntu24.10使用Remmina远程桌面共享

1. ubuntu22.04启用远程桌面共享 点击Remote Desktop,按下图设置 成功启用 2.ubuntu24.10远程桌面启用 选择远程桌面选项 启用远程桌面共享与远程控制 启用远程登陆

基于51单片机的高压锅控制系统proteus仿真

地址&#xff1a; https://pan.baidu.com/s/16BuxmKYUprTGbkEj_BWGvQ 提取码&#xff1a;1234 仿真图&#xff1a; 芯片/模块的特点&#xff1a; AT89C52/AT89C51简介&#xff1a; AT89C52/AT89C51是一款经典的8位单片机&#xff0c;是意法半导体&#xff08;STMicroelectro…

D3的竞品有哪些,D3的优势,D3和echarts的对比

D3 的竞品 ECharts: 简介: ECharts 是由百度公司开发的一款开源的 JavaScript 图表库&#xff0c;提供了丰富的图表类型和高度定制化的配置选项。特点: 易于使用&#xff0c;文档详尽&#xff0c;社区活跃&#xff0c;支持多种图表类型&#xff08;如折线图、柱状图、饼图、散点…

2024年11月13日

1.创业法律指南 留置权和其他三个权 定金和订金 一般保证和连带保证 1.案例 物权编之担保法律制度案例一 冯系养鸡专业户&#xff0c;为改建鸡会和引进良种需资金20万元。冯向陈借款10万元&#xff0c;以自己的一套价值10万元的音响设备抵押&#xff0c;双方立有抵押字据&a…

从电动汽车到车载充电器:LM317LBDR2G 线性稳压器在汽车中的多场景应用

附上LM317系列选型&#xff1a; LM317BD2TG-TO-263 LM317BTG-TO-220 LM317BD2TR4G-TO-263 LM317D2TG-TO-263 LM317D2TR4G-TO-263 LM317TG-TO-220 LM317LBDR2G-SOP-8 LM317LDR2G-SOP-8 LM317MABDTG-TO-252 LM317MABDTRKG-TO-252 LM317MA…

健康之路三度冲击港交所,数字健康医疗平台IPO前景引关注

健康之路股份有限公司&#xff08;HealthyWay Inc.&#xff09;再次向港交所递交招股书&#xff0c;拟在主板上市。此前两次尝试未果&#xff0c;但公司用户基础坚实&#xff0c;业务覆盖广泛&#xff0c;包括健康医疗服务和企业服务及数字营销服务。股东阵容强大&#xff0c;营…

SpringCloud篇(配置中心 - Nacos)

目录 一、Nacos 配置中心 1. 统一配置管理 1.1. 在nacos中添加配置文件 1.2. 从微服务拉取配置 1.2.1. 引入nacos-config依赖 1.2.2. 添加bootstrap.yaml 1.2.3. 读取nacos配置 1.2.4. 页面访问 2. 配置热更新&#xff1a;两种 2.1. 方式一 2.2. 方式二 3. 配置共享…

vue2和vue3的区别详解

vue2 VS vue3 对比vue2vue3配置脚手架cmd命令行可视化方式创建脚⼿架组件通信props、$emit、provide、$arrts、EventBus等props、$emit、provide、inject、arrts等数据监听watch,computedwatch,watchEffect,computed双向绑定Object.definePropertyProxyAPI⽣命周期四个阶段befo…

高中数学:概率-相关运算性质

文章目录 一、概率定义二、运算性质三、事件相互独立四、频率与概率五、练习 一、概率定义 二、运算性质 基本性质 互斥事件的性质 对立事件性质 包含事件的性质 有交集但不包含的事件性质 三、事件相互独立 注意&#xff1a; 四、频率与概率 五、练习

我要学kali-linux之shell脚本编程1

声明&#xff01; 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团队无关&a…

概率密度与功率谱密度的理解与仿真

引言 概率密度&#xff08;Probability Density&#xff09;是统计学中十分重要的概念之一&#xff0c;其应用广泛&#xff1b;功率谱密度&#xff08;power spectral density, PSD&#xff09;则在电子电气行业用得比较多。 在基于雷达的目标检测中&#xff1a;概率密度和功率…