当前位置: 首页 > 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…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

服务器--宝塔命令

一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行&#xff01; sudo su - 1. CentOS 系统&#xff1a; yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...