当前位置: 首页 > news >正文

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

相关文章:

蓝桥杯每日真题 - 第7天

题目&#xff1a;&#xff08;爬山&#xff09; 题目描述&#xff08;X届 C&C B组X题&#xff09; 解题思路&#xff1a; 前缀和构造&#xff1a;为了高效地计算子数组的和&#xff0c;我们可以先构造前缀和数组 a&#xff0c;其中 a[i] 表示从第 1 个元素到第 i 个元素的…...

【Git】Git Clone 指定自定义文件夹名称:详尽指南

目录 引言一、git clone 基本语法二、默认行为&#xff1a;没有指定文件夹名称时三、如何指定自定义文件夹名称四、高级使用技巧&#xff1a;动态文件夹名称4.1 基于日期命名文件夹4.2 基于版本标签&#xff08;Tag&#xff09;动态命名文件夹4.1 基于日期命名文件夹4.2 基于版…...

终端快捷键学习笔记

以下是优化润色后的内容&#xff1a; 终端快捷键学习笔记 前言 终端&#xff08;Terminal&#xff09;是开发者、系统管理员以及技术人员常用的重要工具&#xff0c;它为我们提供了直接与操作系统交互的方式。不同操作系统中的终端使用体验存在差异&#xff0c;尤其在 Linux、…...

Go语言24小时极速学习教程(四)MySQL数据库的增删改查

通过前几篇想必你已经知道该如何使用Go语言写一些简单的程序了&#xff0c;那么从这一篇开始&#xff0c;我们开始探究如何用go语言能够写真正的企业级应用。第一步我们实现先能让程序对数据库进行增删改查&#xff0c;这里以MySQL为例。 1. 导入必要的包 首先需要导入databa…...

04 - Clickhouse-21.7.3.14-2单机版安装

目录 一、准备工作 1、确定防火墙处于关闭状态 2、CentOS 取消打开文件数限制 3、安装依赖 4、CentOS取消SELINUX 二、单机安装 2.1、下载安装 2.2、安装这4个rpm包 2.3、修改配置文件 2.4、启动服务 2.5、关闭开机自启 2.6、使用Client连接server 一、准备工作 1…...

多项式回归

以多元线性回归和特征工程的思想来想出一种称为多项式回归的新算法&#xff0c;它可以让您拟合曲线&#xff0c;非线性函数&#xff0c;您的数据。假设你有一个住房看起来像这样的数据集&#xff0c;其中特征x是以平方英尺为单位的大小。它看起来不像一条直线非常适合这个数据集…...

vscode报错:Connecting with SSH time-out.

当我们在vscode上远程连接&#xff08;Remote_SSH&#xff09;Linux时&#xff0c;如果直接点关闭vscode,下次远程登陆后&#xff0c;就会弹出以下界面&#xff0c; 点击重新加载window就会弹出以下报错&#xff1a; 这是因为我们没有正常关闭remote-ssh, 导致linux上有多个vsc…...

python可视化将多张图整合到一起(画布)

这周有点事忙着&#xff0c;没时间重温刚结束的Mathurcup数学建模&#xff0c;这两天也是再看了下&#xff0c;论文还是赶紧挺烂的&#xff0c;但比国赛又有进步&#xff08;说起国赛又不得不抱怨了&#xff0c;基本其余省份都发了&#xff0c;但江西......哎&#xff09;。哎&…...

C函数如何返回参数lua使用

返回基本数据类型 数字类型&#xff08;整数和浮点数&#xff09; 在C函数中&#xff0c;可以使用lua_pushnumber函数将一个数字&#xff08;整数或浮点数&#xff09;压入Lua栈。当C函数返回后&#xff0c;Lua会从栈顶获取这个数字作为返回值。例如&#xff0c;以下是一个简单…...

pytest在conftest.py中实现用例执行失败进行截图并附到allure测试报告

conftest.py文件简介 conftest.py文件用于定义共享设置、夹具和钩子函数。 可以跨.py文件调用&#xff0c;有多个.py文件调用时&#xff0c;可让conftest.py只调用了一次fixture&#xff0c;或调用多次fixture&#xff1b; conftest.py与运行的用例要在同一个pakage下&#xf…...

编程之路,从0开始:数据在内存中的存储

目录 1、整数在内存中的存储 &#xff08;1&#xff09;大小端 &#xff08;2&#xff09;数据存储读取练习 2、浮点数在内存中的存储 Hello大家好&#xff0c;很高兴我们又见面啦&#xff01;给生活添点Passion,开始今天的编程之路&#xff01; 1、整数在内存中的存储 之…...

二叉树+树的OJ题讲解

求第K层节点个数 思路:走到K1就不走了,一次传回得到的值 #include<stdio.h> #include<stdlib.h> //树的定义 typedef int BTDataType; typedef struct BinaryTreeNode {BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right; }BTNode;//手…...

信捷PLC转以太网连接电脑方法

信捷XC/XD/XL等系列PLC如何上下载程序?可以选择用捷米特JM-ETH-XJ模块轻松搞定,并不需要编程&#xff0c;即插即用&#xff0c;具体看见以下介绍&#xff1a; 产品介绍 捷米特JM-ETH-XJ是专门为信捷PLC转以太网通讯面设计&#xff0c;可实现工厂设备信息化需求&#xff0c;对…...

释放 PWA 的力量:2024 年的现代Web应用|React + TypeScript 示例

在2024年的Web开发领域&#xff0c;PWA&#xff08;Progressive Web Apps&#xff09;已经成为一个不可忽视的技术趋势。这篇文章将探讨PWA的最新发展&#xff0c;并通过实例展示如何构建一个现代PWA应用。 PWA的本质与优势 PWA本质上是一种将Web应用提升到接近原生应用体验的技…...

CVSS4与CVSS3的不同之二

在文章CVSS4与CVSS3的不同-CSDN博客中描述了CVSS3的缺点&#xff0c;以及CVSS4相对CVSS3做了哪些改进和带来了哪些优点。 但是具体CVSS4针对CVSS3做了哪些改动&#xff0c;还没有详细列举出来。 本文主要是针对CVSS4和CVSS的打分的大项和小项进行逐一对比&#xff0c;列出来具体…...

【Pip】如何清理 `pip` 包管理器 —— 完整指南

目录 引言1. 清理 pip 缓存2. 卸载不再需要的包2.1 如何查看已安装的包2.2 如何卸载不需要的包 3. 查看已安装的包及其依赖3.1 查看单个包的依赖3.2 查看所有包的依赖关系3.2 优化包依赖 4. 解决包冲突5. 合并和优化依赖5.1 优化 requirements.txt5.2 删除冗余依赖 6. pip 清理…...

操作数据库

""" 本文件是【连接数据库&#xff1a;通过链和代理查询鲜花信息】章节的配套代码&#xff0c;课程链接&#xff1a;https://juejin.cn/book/7387702347436130304/section/7388065974408183858 您可以点击最上方的“运行“按钮&#xff0c;直接运行该文件&…...

lua-lru缓存算法解析

lua-lru缓存算法解析 主要功能和作用1. 缓存管理&#xff1a;2. 数据存储与访问&#xff1a;3. 迭代器&#xff1a;4. 容量管理&#xff1a; 具体实现细节使用场景使用示例 lua-lru 是 Lua 语言中的一个 LRU&#xff08;Least Recently Used&#xff0c;最近最少使用&#xff0…...

Python - 初识Python;Python解释器下载安装;Python IDE(一)

一、初识Python Python 是一种高级编程语言&#xff0c;Python是一种面向对象的解释型计算机程序设计语言&#xff0c;Python由荷兰国家数学与计算机科学研究中心的吉多范罗苏姆&#xff08;&#xff09;Guido van Rossum吉多范罗苏姆&#xff08;&#xff09;于1989 年底发明…...

鸿蒙学习基本概念

文章目录 1、当前移动应用开发中遇到的主要挑战包括&#xff1a;2、 新的应用生态应该具备如下特征&#xff1a;3、HarmonyOS 应用&#xff1a;使用 HarmonyOS SDK 开发的应用程序&#xff0c;能够在华为终端设备4、HarmonyOS 元服务&#xff1a;元服务是 HarmonyOS 面向万物互…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

【FTP】ftp文件传输会丢包吗?批量几百个文件传输,有一些文件没有传输完整,如何解决?

FTP&#xff08;File Transfer Protocol&#xff09;本身是一个基于 TCP 的协议&#xff0c;理论上不会丢包。但 FTP 文件传输过程中仍可能出现文件不完整、丢失或损坏的情况&#xff0c;主要原因包括&#xff1a; ✅ 一、FTP传输可能“丢包”或文件不完整的原因 原因描述网络…...

结构化文件管理实战:实现目录自动创建与归类

手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题&#xff0c;进而引发后续程序异常。使用工具进行标准化操作&#xff0c;能有效降低出错概率。 需要快速整理大量文件的技术用户而言&#xff0c;这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB&#xff0c;…...