当前位置: 首页 > 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 面向万物互…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...