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

【蓝桥杯每日一题】重新排序

重新排序

2024-12-8 蓝桥杯每日一题 重新排序 前缀和 差分

题目大意

给定一个数组 A 和一些查询 L i , R i Li_,R_i Li,Ri, 求数组中第 L i L_i Li至第 R i R_i Ri个元素之和。

小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可 以增加多少?

解题思路

首先看到题一定会想到前缀和,因为要求数组中某一个区间的和。

分析这个题,想要某些区间里的和达到最大,那么可以让那些重合计算的位置能够交换到最大的值,以此达目的。

然后就是计算每一个位置的使用使用次数,可以通过差分,这里涉及到对某些区间的一个 +1 。

最后想要给这些使用次数最多的分配到可行的最大值,那么可以通过排序,将原数组和使用的次数都进行一个排序,那么这时候就满足上述那个要求;然后分别计算两次的总和相减即可。

举例:

1 2 3 4 5    	1 3   2 5
1 2 2 1 1 排序:	
1 2 3 4 5 
1 1 1 2 2
Accepted
//  不开 long long 见祖宗
#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 100010;
ll a[N],b[N],c[N];
ll n,m;void diff(int l,int r) {b[l] += 1;b[r + 1] -= 1;
}int main()
{cin>>n;for(int i = 1 ;i <= n ;i++ ) {cin>>a[i];c[i] = c[i-1] + a[i];}cin>>m;ll cnt = 0;for(int i = 1;i <= m;i++) {int l,r;cin>>l>>r;diff(l,r);cnt += c[r] - c[l-1];}for(int i = 1;i <= n;i++) {b[i] = b[i-1] + b[i];}sort(b+1,b+n+1);sort(a+1,a+n+1);ll pre = 0;for(int i = 1;i <= n;i++) {pre += a[i] * b[i];}cout<<pre - cnt<<endl;return 0;
}
思考

当时的思考已经分析到了使用次数,就差最后的一个神来之笔——排序求解。

备注

想要一起备赛的小伙伴可以私信加我的联系方式!

相关文章:

【蓝桥杯每日一题】重新排序

重新排序 2024-12-8 蓝桥杯每日一题 重新排序 前缀和 差分 题目大意 给定一个数组 A 和一些查询 L i , R i Li_,R_i Li,​Ri​, 求数组中第 L i L_i Li​至第 R i R_i Ri​个元素之和。 小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查 询结果的和尽可能…...

《深入浅出HTTPS》读书笔记(16):消息验证码算法分类

MAC算法有两种形式&#xff0c;分别是CBC-MAC算法和HMAC算法。 CBC-MAC算法从块密码算法的CBC分组模式演变而来&#xff0c;简单地说就是最后一个密文分组的值就是MAC值。 HMAC&#xff08;Hash-based Message Authentication Code&#xff09;算法使用Hash算法作为加密基元&am…...

如何使用Apache HttpClient来执行GET、POST、PUT和DELETE请求

Apache HttpClient 是一个功能强大且灵活的库&#xff0c;用于在Java中处理HTTP请求。 它支持多种HTTP方法&#xff0c;包括GET、POST、PUT和DELETE等。 本教程将演示如何使用Apache HttpClient来执行GET、POST、PUT和DELETE请求。 Maven依赖 要使用Apache HttpClient&…...

数据结构-希尔排序

每次对5个间隔的元素进行插入排序&#xff0c;然后间隔依次递减&#xff0c;直到间隔为1 互质&#xff1a;相邻的两个元素没有公因子 这个例子只有间隔1起来作用 #include<iostream> using namespace std; typedef int ElmentType; void shell_Sort(ElmentType A[], int…...

Spire.doc 合并word,复制word

之前使用的poi来实现这个功能&#xff0c;然后发现在复制chart时&#xff0c;边框样式无法修改&#xff0c;于是就使用了spire.doc 1. 引入依赖 <repositories><repository><id>com.e-iceblue</id><name>e-iceblue</name><url>https…...

【Spring项目】表白墙,留言板项目的实现

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 一&#xff1a;项目实现准备 1&#xff1a;需求 2&#xff1a;准备工作 &#xff08;1&#xff09;…...

分布式事务-nacos/seata在windows环境下部署及开发

参考资料&#xff1a; nacos的windows环境部署 seata和nacos的结合及seata开发 参考demo及资料 nacos在windows环境下的部署&#xff1a; nacos在windows下的部署参考文章 seata加入nacos配置&#xff1a; 首先下载seata安装包&#xff1a;Release v1.7.0(Not Apache relea…...

分布式微服务架构下的密码安全性方案

在 Spring Cloud 微服务架构中&#xff0c;涉及登录或注册时的密码安全性问题&#xff0c;通常需要从传输过程中的安全性和存储过程中的安全性两个方面进行保护。以下是主流的安全性保证方案&#xff1a; 传输过程中的安全性 HTTPS 加密传输&#xff1a; 使用 HTTPS 协议来保…...

基于pytorch的深度学习基础4——损失函数和优化器

四&#xff0e;损失函数和优化器 4.1 均值初始化 为减轻梯度消失和梯度爆炸&#xff0c;选择合适的权重初值。 十种初始化方法 Initialization Methods 1. Xavie r均匀分布 2. Xavie r正态分布 4. Kaiming正态分布 5. 均匀分布 6. 正态分布 7. 常数分布 8. 正交矩阵初…...

网络安全信息收集(总结)更新

目录 重点&#xff1a; 前言&#xff1a; 又学到了&#xff0c;就是我们什么时候要子域名收集&#xff0c;什么时候收集域名&#xff0c;重点应该放前面 思考&#xff1a; 信息收集分为哪几类&#xff0c;什么是主域名&#xff0c;为什么要收集主域名&#xff0c;为什么要收…...

web斗地主游戏实现指北

前后端通信 作为一个即时多人游戏&#xff0c;不论是即时聊天还是更新玩家状态&#xff0c;都需要服务端有主动推送功能&#xff0c;或者客户端轮询。轮询的时间间隔可能导致游玩体验差&#xff0c;因为不即时更新&#xff0c;而且请求数量太多可能会打崩服务器。 建议在cs间…...

SpringMVC其他扩展

一、全局异常处理机制: 1.异常处理两种方式: 开发过程中是不可避免地会出现各种异常情况的&#xff0c;例如网络连接异常、数据格式异常、空指针异常等等。异常的出现可能导致程序的运行出现问题&#xff0c;甚至直接导致程序崩溃。因此&#xff0c;在开发过程中&#xff0c;…...

【Linux】网络服务

声明&#xff0c;以下内容均学习自《Linux就该这么学》一书 1、创建网络会话 Linux系统使用NetworkManager提供网络服务&#xff0c;它是一种动态管理网络配置的守护进程&#xff0c;能够让网络设备保持连接状态。 nmcli nmcli是一款基于命令行的网络配置工具&#xff0c;它…...

工作:SolidWorks从3D文件导出2D的DWG或DXF类型文件方法

工作&#xff1a;SolidWorks从3D文件导出2D的DWG或DXF类型文件方法 SolidWorks从3D文件导出2D的DWG或2D DXF类型文件方法&#xff08;一&#xff09;打开3D文件&#xff08;二&#xff09;从装配体到工程图&#xff08;三&#xff09;拖出想要的角度的图型&#xff08;四&#…...

IDL学习笔记(五)MODIS数据(Grid)

IDL学习笔记&#xff08;四&#xff09; MODIS Grid数据的重投影 正弦投影 是以 米 为单位的 经纬度网格 是以 度 为单位的 但是转换之后&#xff0c;不会一一对应&#xff0c;所以需要对中间空缺位置需要进行一个填补。 核心问题: 把一个点从一个空间参考系放到另一个空间参…...

JavaScript语言介绍

JavaScrip是一门编程语言 浏览器的工作原理 所以得域名都会被解析成ip地址&#xff0c;ip地址就是服务器地址&#xff0c;服务器地址会返回一个html文件&#xff0c;解析html遇到css文件和JavaScript标签就会把相应内容下载下来进行解析。 认识浏览器的内核 浏览器的渲染过程 …...

Lua使用点号和冒号的区别

首先建立一个table&#xff0c;再分别定义两个方法&#xff0c;如下&#xff1a; local meta {}function meta:test1(...)print(self)print("")for k,v in pairs({...}) doprint(v)end endfunction meta.test2(...)print(self)print("")for k,v in pairs…...

LLM - 开源视觉多模态 LLaVA-CoT(o1) 深度推理模型 测试与源码 教程

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/144304351 免责声明&#xff1a;本文来源于个人知识与公开资料&#xff0c;仅用于学术交流&#xff0c;欢迎讨论&#xff0c;不支持转载。 LLaVA-…...

Ansible的yum和saltstack的哪个功能相似

Ansible的yum和saltstack的哪个功能相似 在 Ansible 和 SaltStack 中&#xff0c;Ansible 的 yum 模块 和 SaltStack 的 pkg 模块 功能相似。它们都用于管理软件包&#xff0c;支持安装、升级、删除和查询等操作。 Ansible 的 yum 模块 用途&#xff1a; 专门用于基于 Red Hat …...

paimon0.9记录

启动paimon -- 本地模式演示 bin/start-cluster.sh-- 启动sqlclient bin/sql-client.sh示例 -- 创建catalog&#xff0c;每次都要创建&#xff0c;创建一个已经存在的catalog相当于使用 CREATE CATALOG fs_catalog WITH (typepaimon,warehousefile:/data/soft/paimon/catalog…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...