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

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

遍历 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…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

4. TypeScript 类型推断与类型组合

一、类型推断 (一) 什么是类型推断 TypeScript 的类型推断会根据变量、函数返回值、对象和数组的赋值和使用方式&#xff0c;自动确定它们的类型。 这一特性减少了显式类型注解的需要&#xff0c;在保持类型安全的同时简化了代码。通过分析上下文和初始值&#xff0c;TypeSc…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...