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

Boss-Key:Windows用户必备的窗口隐私保护神器,告别尴尬瞬间

Boss-Key&#xff1a;Windows用户必备的窗口隐私保护神器&#xff0c;告别尴尬瞬间 【免费下载链接】Boss-Key 老板来了&#xff1f;快用Boss-Key老板键一键隐藏静音当前窗口&#xff01;上班摸鱼必备神器 项目地址: https://gitcode.com/gh_mirrors/bo/Boss-Key 你是不…...

开源智能体框架xbrain:模块化设计与工程实践指南

1. 项目概述&#xff1a;一个面向开发者的开源智能体框架最近在开源社区里&#xff0c;一个名为xbrain的项目引起了我的注意。它由开发者yuruotong1发起&#xff0c;定位是一个“开源智能体框架”。简单来说&#xff0c;它试图为开发者提供一个工具箱&#xff0c;让构建、管理和…...

ARM SCTLR2_EL2寄存器解析与虚拟化安全控制

1. ARM SCTLR2_EL2寄存器架构解析SCTLR2_EL2是ARMv8/v9架构中EL2&#xff08;Hypervisor&#xff09;级别的扩展系统控制寄存器&#xff0c;作为标准SCTLR_EL2的补充&#xff0c;它通过掩码位机制实现了对关键系统功能的细粒度控制。这个64位寄存器主要包含两类功能字段&#x…...

不只是安装:在龙芯2k1000LA上为Loongnix配置WiFi、蓝牙与触摸屏驱动的完整流程

龙芯2k1000LA开发板外设驱动深度配置指南&#xff1a;从WiFi到触摸屏的全栈解决方案 在国产化硬件开发领域&#xff0c;龙芯2k1000LA开发板凭借其完全自主的LoongArch架构&#xff0c;正成为物联网和嵌入式设备开发者的重要选择平台。不同于x86架构的"开箱即用"体验&…...

Botty:暗黑2重制版自动化助手,告别重复刷图的终极方案

Botty&#xff1a;暗黑2重制版自动化助手&#xff0c;告别重复刷图的终极方案 【免费下载链接】botty D2R Pixel Bot 项目地址: https://gitcode.com/gh_mirrors/bo/botty 你是否厌倦了在《暗黑破坏神2&#xff1a;重制版》中反复刷图、手动拾取、机械操作&#xff1f;每…...

AMD NPU加速GPT-2微调:边缘AI训练实战解析

1. AMD NPU与客户端AI训练的技术背景在AI模型部署领域&#xff0c;边缘计算正经历着从单纯推理到完整训练工作流的范式转变。传统上&#xff0c;像GPT-2这样的语言模型训练完全依赖云端GPU集群&#xff0c;但这种方式存在数据隐私泄露、网络延迟和持续服务依赖等固有缺陷。AMD …...

Claude模型配置管理工具:从原理到实践,构建高效AI应用

1. 项目概述&#xff1a;一个为Claude模型量身定制的配置管理工具最近在折腾大语言模型本地部署和API调用时&#xff0c;我发现一个挺普遍的问题&#xff1a;虽然像Claude这样的模型能力很强&#xff0c;但每次想切换不同的使用场景——比如从写代码切换到写文案&#xff0c;或…...

CM201-1-CH刷机避坑指南:S905L3B+UWE5621DS芯片组合刷机时,为什么必须取消‘擦除flash’?

CM201-1-CH刷机避坑指南&#xff1a;S905L3BUWE5621DS芯片组合的特殊性解析 每次刷机操作都像一场精密手术&#xff0c;而CM201-1-CH这款搭载S905L3B主控与UWE5621DS无线芯片组合的机顶盒&#xff0c;则像一位"特殊体质"的患者——常规操作可能导致不可逆的"医疗…...

高速串行链路均衡技术解析与工程实践

1. 高速串行链路均衡技术概述在现代数字通信系统中&#xff0c;高速串行数据链路是实现高带宽数据传输的核心技术。随着数据速率攀升至6.25Gbps甚至更高&#xff0c;信号在传输过程中会遭遇严重的信道损耗问题。典型FR4 PCB走线在6.25Gbps速率下&#xff0c;第一谐波处的插入损…...

朋升爱生活

我爱生活。...