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

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

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

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

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...