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

【16届蓝桥杯寒假刷题营】第1期DAY5

news 来源：原创 2025/6/8 11:03:58

5.依依的询问最小值 - 蓝桥云课

问题描述

依依有个长度为 n 的序列 a，下标从 1 开始。

她有 m 次查询操作，每次她会查询下标区间在 [li,ri] 的 a 中元素和。她想知道你可以重新排序序列 a，使得这 m 次查询的总和最小。

求你求出 m 次查询总和的最小值。

输入格式

第一行输入两个整数 n,m (1≤n,m≤105)，表示序列 a 的长度以及查询次数。

第二行输入 n 个整数 ai (1≤ai≤105)，表示序列 a 中的元素。

接下来 m 行，每行输入两个整数 li,ri (1≤li≤ri≤n)，表示询问的下标区间。

输出格式

输出仅一行，包含一个整数，表示 m 次查询总和的最小值。

样例输入

样例输出

思路：

方法一:

下标次数越多说明对应的数值就要最小，这样m 次查询总和就最小。所以我们要记录每一个下标出现的次数降序排序，输入数组的值升序排序。用sum记录它们一一对应相乘和相加即可。但是当m，n很大的时候时间复杂度很高，数值也很大，会失进度和超时。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1e5+10;
int n,m;
int arr[N];
int has[N];
bool compare(int a,int b)
{return a > b;
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(int i = 1 ; i <= n ; i++){cin >> arr[i];}int l,r;while(m--){cin >> l >> r;for(int j = l ; j <= r ; j++){has[j]++;}}sort(has + 1, has + 1 + n,compare);//对has数组降序 sort(arr + 1,arr + 1 + n);//对arr数组升序排序int sum = 0;for(int i = 1 ; i <= n ; i++){sum += arr[i] * has[i];	} cout << sum;}

方法二：
面对这种区间问题，我们需要用到差分数组优化。差分数组可以很好的将一个区间同时增加，减少。对于这道题只有增加出现次数的下标。所以差分数组一开始都为0。待到全部区间操作完毕，用 dif[i] += dif[i - 1]; // 累加差分数组得到实际频率。得到实际数组。

代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const ll N = 1e5+10;
ll n,m;
ll arr[N];
ll dif[N];
bool compare(ll a,ll b)
{return a > b;
}
int main(void)
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m;for(ll i = 1 ; i <= n ; i++){cin >> arr[i];}ll l,r;while(m--){cin >> l >> r;dif[l] += 1;if(r+1 <= n)//注意边界dif[r+1] -= 1;	}//通过差分数组实现原本数组for (ll i = 1; i <= n; i++){dif[i] += dif[i - 1];  // 累加差分数组得到实际频率}sort(dif + 1, dif + 1 + n,compare);//对dif数组降序 sort(arr + 1,arr + 1 + n);//对arr数组升序排序ll sum = 0;for(ll i = 1 ; i <= n ; i++){sum += arr[i] * dif[i];	} cout << sum;}

【16届蓝桥杯寒假刷题营】第1期DAY5

5.依依的询问最小值 - 蓝桥云课问题描述依依有个长度为 n 的序列 a，下标从 1 开始。她有 m 次查询操作，每次她会查询下标区间在 [li,ri] 的 a 中元素和。她想知道你可以重新排序序列 a，使得这 m 次查询的总和最小。求你求出 m 次…...

编程日记 2025/6/3 22:05:04

.NET周刊【1月第1期 2025-01-05】

国内文章 3款.NET开源、功能强大的通讯调试工具，效率提升利器！ https://www.cnblogs.com/Can-daydayup/p/18631410 本文介绍了三款功能强大的.NET开源通讯调试工具，旨在提高调试效率。这些工具包括LLCOM，提供串口调试和自动化处…...

编程日记 2025/6/3 22:03:43

（7）(7.2) 围栏

文章目录前言 1 通用设置 2 围栏类型 3 破坏栅栏行动 4 使用 RC 通道辅助开关启用栅栏 5 自动高度规避 6 在任务规划器中启用围栏 7 用于遥控飞行训练 8 MAVLink 支持前言 ArduPilot 支持基于本机的圆柱形（“TinCan”）和多边形和/或圆柱形、…...

编程日记 2025/6/3 5:10:43

A summit (峰会) is a meeting of heads of state or government. Arranging the rest areas for the summit is not a simple job. The ideal arrangement of one area is to invite those heads so that everyone is a direct friend of everyone. Now given a set of tenta…...

编程日记 2025/6/3 22:04:48

linux_socket

udp 通信 server #include <iostream> #include <arpa/inet.h> #include <unistd.h> #include <cstring>using namespace std;#define UPORT 12511int main(){int sock socket(AF_INET, SOCK_DGRAM, 0); // 创建一个UDP套接字if (sock -1) {cout&…...

编程日记 2025/6/3 22:05:36

Linux探秘坊-------3.开发工具详解（2）

1.动静态库和动静态链接（操作） 静态库是指编译链接时,把库⽂件的代码全部加⼊到可执⾏⽂件中,因此⽣成的⽂件⽐较⼤,但在运⾏时也就不再需要库⽂件了。其后缀名⼀般为“.a” 动态库与之相反,在编译链接时并没有把库⽂件的代码加⼊到可执⾏⽂件中 ,⽽…...

编程日记 2025/6/3 22:05:54

Mysql InnoDB B+Tree是什么？

“mysql中常用的数据库搜索引擎InnoDB,其索引通过BTree的方式进行构建。” 实在想不起来BTree是怎么一回事了。以点带线，将涉及到的数据结构一起复习一下。文章目录数据结构定义红黑树定义使命 BTree定义使命 BTree定义 InnoDB BTree 旋转与调整二叉排序树插入删…...

编程日记 2025/6/3 22:04:15

C语言进阶习题【1】指针和数组（1）——一维数组

1. 数组名的意义： sizeof(数组名)，这里的数组名表示整个数组，计算的是整个数组的大小。&数组名，这里的数组名表示整个数组，取出的是整个数组的地址。除此之外所有的数组名都表示首元素的地址。（一维数…...

编程日记 2025/6/3 22:05:20

2024：成长、创作与平衡的年度全景回顾

文章目录 1.前言2.突破自我：2024年个人成长与关键突破3.创作历程：从构想到落笔，2024年的文字旅程4.生活与学业的双重奏：如何平衡博客事业与个人生活5.每一步都是前行：2024年度的挑战与收获6.总结 1.前言回首2024年&a…...

编程日记 2025/6/3 4:05:27

【Linux】网络基础探索：开启你的网络之旅

🌈 个人主页：Zfox_ 🔥 系列专栏：Linux 目录一：🔥 计算机网络背景 🦋 1-1 网络发展二：🔥 初识协议 🦋 2-1 协议分层协议分层 vs. 软件分层 🦋 2-…...

编程日记 2025/6/3 22:04:32

function isBulkReadStatement, file SQLiteDatabaseTracking.cpp

一问题：Xcode16.0运行在iPhone16/ios18.0 以上发生闪退， 闪退在 YYCache–>YYKVStorage 文件内。以上删除保以下错误： function isBulkReadStatement, file SQLiteDatabaseTracking.cpp 解决方案： 找到YYKVStorage文件中_d…...

编程日记 2025/6/4 3:09:14

React 中hooks之useTransition使用总结

目录概述基本用法使用场景最佳实践注意事项概述什么是 useTransition? useTransition 是 React 18 引入的新 Hook，用于标记非紧急的状态更新。它允许组件在状态转换期间保持响应，通过将某些更新标记为"过渡"来推迟它们的渲染。主要特…...

编程日记 2025/6/4 3:08:11

leetcode 3097. 或值至少为 K 的最短子数组 II 中等

给你一个非负整数数组 nums 和一个整数 k 。如果一个数组中所有元素的按位或运算 OR 的值至少为 k ，那么我们称这个数组是特别的。请你返回 nums 中最短特别非空子数组的长度，如果特别子数组不存在，那么返回 -1 。示例 1&…...

编程日记 2025/5/31 10:51:57

C# OpenCV机器视觉:特征匹配 “灵魂伴侣”

在一个阳光仿佛被施了魔法，欢快得直蹦跶的早晨，阿强像个即将踏上神秘寻宝之旅的探险家，一屁股墩在实验室那张堆满各种奇奇怪怪小玩意儿的桌前。桌上，零件、线路、半成品设备乱成一团，唯有他那宝贝电脑屏幕散发着清冷又…...

编程日记 2025/6/4 3:08:59

DDD - 整洁架构_解决技术设计困局

文章目录 Pre如何落地 DDD底层技术的更迭整洁架构的设计主动适配器/北向适配器被动适配器/南向适配器整洁架构的落地总结 Pre DDD - 软件退化原因及案例分析 DDD - 如何运用 DDD 进行软件设计 DDD - 如何运用 DDD 进行数据库设计 DDD - 服务、实体与值对象的两种设计思路…...

编程日记 2025/6/4 4:11:42

金融项目实战 07|Python实现接口自动化——连接数据库和数据清洗、测试报告、持续集成

目录一、投资模块（投资接口投资业务） 二、连接数据库封装和清洗数据 1、连接数据库 2、数据清洗 4、调用三、批量执行测试用例并生成测试报告四、持续集成 1、代码上传gitee 2、Jenkin持续集成一、投资模块（投资接口投资业务…...

编程日记 2025/5/31 10:35:53

Ceph与RAID在存储中的协同工作过程

本文将结合架构图，详细讲解Ceph与RAID如何在存储环境中相互配合，共同提供高效且可靠的存储服务。架构概述从上图中可以看到，Ceph的架构主要分为四个层次： 客户端和服务接口层：这一层包括客户端访问存储应用的接口…...

编程日记 2025/6/3 7:03:54

《重生到现代之从零开始的C++生活》—— 类和对象2

类的默认成员函数默认成员函数就是用户没有显示实现，编译器会自动生成的成员函数，一个类会默认生成6个成员函数构造函数构造函数时特殊的成员函数，构造函数的初始化对象函数名与类名相同没有返回值对象实例化的时候胡自动调用构造…...

编程日记 2025/6/3 10:36:22

MFC 使用 32位带Alpha通道的位图

最近需要做一个MFC界面上的图片，众所周知，MFC 好像只支持 bmp 格式的！先看我的原始24位图片，RGB 三个颜色各占8位（256色），所以是24位。如果放到MFC界面上，是这个很丑的效果它是一个正方形图片，周围的白色可以看见。解下来，进入今天的主题： 32位带 Alpha 通…...

编程日记 2025/6/3 23:02:50

QT：子控件VLC播放视频时，父控件无法截取鼠标事件

具体来说： 反复验证，结论正确。只要是播放区（即传递给VLC的窗口区域），就无法点击。比如WidgetA，新建一个WidgetB，设置位置时留有一点边框。这个时候WidgetA的边框区是能收到鼠标事件的。这…...

编程日记 2025/6/4 3:08:43

力扣 739. 每日温度

🔗 https://leetcode.cn/problems/daily-temperatures 题目给定一个数组，表示每天的天气返回一个数组，index i 表示几天后比当前的温度要高，没有则为 0 思路维护一个单调递减栈，若当前的温度比栈顶大&#xff0c…...

编程日记 2025/6/3 1:30:50

蓝桥杯阶乘的和（C++完整代码+详细分析）

题目描述原题链接阶乘的和问题描述给定 n 个数 Ai，问能满足 m! 为 ∑(Ai!) 的因数的最大的 m 是多少。其中 m! 表示 m 的阶乘，即 123⋯m。输入格式输入的第一行包含一个整数 n。第二行包含 n 个整数，分别表示 Ai，相…...

编程日记 2025/6/2 23:37:09

OpenAI进军实体机器人：GPT赋能的智能未来

近年来，人工智能技术飞速发展，深刻地改变着我们的生活。而OpenAI作为人工智能领域的领军者，其最新动作更是引人注目：进军实体机器人领域！这不仅标志着人工智能技术应用场景的重大拓展，也预示着未来智能机器…...

编程日记 2025/6/3 13:10:56

【Python运维】用Python管理Docker容器：从`docker-py`到自动化部署的全面指南

《Python OpenCV从菜鸟到高手》带你进入图像处理与计算机视觉的大门！解锁Python编程的无限可能：《奇妙的Python》带你漫游代码世界在现代软件开发和运维过程中，Docker容器化技术因其高效、轻量和可移植性而被广泛应用。Python作为一种灵活且功能强大的编程语言，通过doc…...

编程日记 2025/6/3 16:15:01

【机器学习实战入门项目】MNIST数字分类机器学习项目

Python 深度学习项目：手写数字识别为了使机器更加智能，开发者们正在深入研究机器学习和深度学习技术。人类通过不断练习和重复来学习执行某项任务，从而记住如何完成这些任务。然后，大脑中的神经元会自动触发，他们能够…...

编程日记 2025/6/3 10:36:35

【统计信号处理基础——估计与检测理论】Vol1.Ch1 引言

文章目录 1. 信号处理中的估计2. 估计的数学问题3. 估计量性能评估习题1.11.21.31.41.5 1. 信号处理中的估计从离散时间波形或一组数据集中提取参数的问题。我们有 N N N点数据集 { x [ 0 ] , x [ 1 ] , ⋯ , x [ N − 1 ] } \{x[0],x[1],\cdots,x[N-1]\} {x[0],x[1],⋯,x[N−…...

编程日记 2025/6/3 16:16:05

Linux 存储设备和 Ventoy 启动盘制作指南

一、Linux 存储设备基础知识 1. 设备路径（/dev） 设备路径是 Linux 系统中物理存储设备的唯一标识，类似设备的"身份证号"。命名规则解析 /dev/sda： /dev：device（设备）的缩写&…...

编程日记 2025/6/3 16:14:46

第14章：Python TDD应对货币类开发变化（一）

写在前面这本书是我们老板推荐过的，我在《价值心法》的推荐书单里也看到了它。用了一段时间 Cursor 软件后，我突然思考，对于测试开发工程师来说，什么才更有价值呢？如何让 AI 工具更好地辅助自己写代码，或许…...

编程日记 2025/6/3 16:15:33

网络协议入门：OSI模型与TCP/IP栈

在网络通信的世界中，数据从一台设备传输到另一台设备，需要遵循一系列规则，这些规则统称为网络协议。OSI模型和TCP/IP协议栈作为网络通信的基石，帮助我们理解数据传输的全流程。这篇文章将深入解析它们的结构、功能和实际应用&…...

编程日记 2025/6/3 16:14:30

pthread_exit函数

pthread_exit 是 POSIX 线程库（pthread）中的一个函数，用于显式地终止调用线程。与 exit 函数不同，pthread_exit 仅影响调用它的线程，而不是整个进程。使用 pthread_exit 可以确保线程在退出时能够正确地释放线程相关的…...

编程日记 2025/6/2 6:51:53

从语音识别到图像识别：AI如何“看”和“听”

引言随着人工智能技术的不断进步，AI的“听”和“看”能力正变得越来越强大。从语音识别到图像识别，AI不仅能够通过声音与我们互动，还能通过视觉理解和分析周围的世界。这些技术不仅改变了我们与机器的交互方式，也在各行各业中带…...

编程日记 2025/6/4 4:49:38

UML-对象图（Object Diagram）

定义在UML（统一建模语言）中，对象图用于描述在某一时刻，一组对象以及它们之间关系的图形。它是系统详细状态在某一时刻的快照，常用于表示复杂的类图的一个实例。关联、依赖和继承是对象图中常见的三种关系，下面将对这三种关系进行详细说明，并阐述它们之间的区别。 Pla…...

编程日记 2025/6/3 10:36:34

Pytorch - YOLOv11自定义资料训练

►前言本篇将讲解目前最新推出的YOLOv11搭配Roboflow进行自定义资料标注训练流程，透过Colab上进行实作说明，使大家能够容易的了解YOLOv11的使用。 ►YOLO框架下载与导入 ►Roboflow的资料收集与标注进行自定义资料集建置与上传透过Roboflow工具进行…...

编程日记 2025/6/4 4:51:16

大模型GUI系列论文阅读 DAY2续2：《使用指令微调基础模型的多模态网页导航》

摘要自主网页导航的进展一直受到以下因素的阻碍： 依赖于数十亿次的探索性交互（通常采用在线强化学习），依赖于特定领域的模型设计，难以利用丰富的跨领域数据进行泛化。在本研究中，我们探讨了基于视觉-语…...

编程日记 2025/6/4 4:50:44

Docker 搭建mysql 连接超时问题，xxl-job启动mysql连接报错，禁用dns

1.本地连接Navicat报错信息，猜测是navicat默认连接超时导致的，后面换成idea一个插件虽然慢但连接上了 2013 - Lost connection to MySQL server at reading initial communication packet 2.启动xxl-job会报错，网上有人mysql驱动与数据库不匹…...

编程日记 2025/6/2 17:57:20

SSM课设-学生管理系统

【课设者】SSM课设-学生管理系统技术栈: 后端: SpringSpringMVCMybatisMySQLJSP 前端: HtmlCssJavaScriptEasyUIAjax 功能: 学生端: 登陆学生信息管理个人信息管理老师端: 多了教师信息管理管理员端: 多了班级信息管理多了年级信息管理多了系统用户管理...

编程日记 2025/6/4 4:49:54

JavaScript笔记APIs篇03——DOM节点Bom操作本地存储正则表达式

黑马程序员视频地址：黑马程序员前端JavaScript入门到精通全套视频教程https://www.bilibili.com/video/BV1Y84y1L7Nn?vd_source0a2d366696f87e241adc64419bf12cab&spm_id_from333.788.videopod.episodes&p78https://www.bilibili.com/video/BV1Y84y1L7Nn?…...

编程日记 2025/5/30 23:19:30

JS 有哪些模块化规范

一、CommonJS 规范 1. 主要应用场景主要用于服务器端开发，尤其是 Node.js 环境。 2. 核心思想使用 require() 函数来引入模块，使用 module.exports 或 exports 对象来导出模块中的内容。 // math.js 模块const add (a, b) > a b;const subtr…...

编程日记 2025/6/4 4:51:00

摘录人工智能面试笔试题汇总

一、人工智能面试问答题汇总 1、什么是人工智能？ 人工智能（AI）是一种计算机科学，它增强了像人类一样工作和反应的智能机器。机器模拟人类智能行为的能力。人工智能通常用于各种应用，如决策、语音识别、感知、认知能力…...

编程日记 2025/6/4 4:50:09

【PCIe 总线及设备入门学习专栏 6.1 -- PCIe MCTP】

文章目录 1 什么是 MCTP？2 MCTP 消息在 PCIe 中的传输特点3 PCIe MCTP 的局限性(1) 出站（Outbound）MCTP 消息分解的限制(2) 入站（Inbound）MCTP 消息组装的限制4 MCTP 消息的实际使用流程发送端处理流程接收端处理流程5 实际使用场景例 1：管理命令传输例 2：监控数据报告例…...

编程日记 2025/6/4 4:50:25

RabbitMQ集群安装rabbitmq_delayed_message_exchange

1、单节点安装rabbitmq安装延迟队列安装延迟队列rabbitmq_delayed_message_exchange可以参考这个文章： rabbitmq安装延迟队列-CSDN博客 2、集群安装rabbitmq_delayed_message_exchange 在第二个节点 join_cluster 之后，start_app 就会报错了 (CaseC…...

编程日记 2025/6/3 5:01:10

doris 2.1 Queries Acceleration-Hints 学习笔记

1 Hint Classification 1.1 Leading Hint：Specifies the join order according to the order provided in the leading hint. 1.2 Ordered Hint：A specific type of leading hint that specifies the join order as the original text sequence. 1.3 Distribute Hint：Speci…...

编程日记 2025/6/3 13:45:30

5.依依的询问最小值 - 蓝桥云课

问题描述

输入格式

输出格式

样例输入

样例输出

思路：

代码如下：

相关文章：