蓝桥杯备赛-差分-重新排序
问题描述
给定一个数组 AA 和一些查询 Li,RiLi,Ri, 求数组中第 LiLi 至第 RiRi 个元素之和。
小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可 以增加多少?
输入格式
输入第一行包含一个整数 nn 。
第二行包含 nn 个整数 A1,A2,⋯,AnA1,A2,⋯,An, 相邻两个整数之间用一个空格分隔。
第三行包含一个整数 mm 表示查询的数目。
接下来 mm 行, 每行包含两个整数 Li、RiLi、Ri, 相邻两个整数之间用一个空格分 隔。
输出格式
输出一行包含一个整数表示答案。
样例输入
5
1 2 3 4 5
2
1 3
2 5
样例输出
4
样例说明
原来的和为 6+14=206+14=20, 重新排列为 (1,4,5,2,3)(1,4,5,2,3) 后和为 10+14=2410+14=24, 增 加了 4。
评测用例规模与约定
对于 30%30% 的评测用例, n,m≤50n,m≤50;
对于 50%50% 的评测用例, n,m≤500n,m≤500;
对于 70%70% 的评测用例, n,m≤5000n,m≤5000;
对于所有评测用例, 1≤n,m≤105,1≤Ai≤106,1≤Li≤Ri≤1061≤n,m≤105,1≤Ai≤106,1≤Li≤Ri≤106 。
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//计算每个位置的查询次数,查询次数最多的放最大的数字
//注意查询和要用long long
//差分--对于一段区间的操作--先在差分数组上做标记--再利用a[i]=a[i-1]+d[i]---重置a数组
//cha是d的前缀和数组,d是cha的差分数组
int main() {int n;cin >> n;vector<int> a(n + 5, 0);vector<int> cha(n + 5, 0);vector<int> d(n + 5, 0);for (int i = 1; i <= n; i++) {cin >> a[i];}//初始化a数组int m;cin >> m;int l, r;for (int i = 1; i <= m; i++) {cin >> l >> r;d[l]++;d[r + 1]--;}//初始化差分数组for (int i = 1; i <= n; i++) {cha[i] = cha[i - 1] + d[i];}//更新cha数组long long sum1 = 0;long long sum2 = 0;for (int i = 1; i <= n; i++){sum1 += (long long)a[i] * cha[i];
//将 sum1 += a[i] * cha[i]; 改为 sum1 += (long long)a[i] * cha[i]; 原因在于数据类型的溢出问题。当 a[i] 和 cha[i] 的值较大时,a[i] * cha[i] 的结果可能会超出 int 类型的表示范围(int 通常是 32 位,范围是 -2^31 到 2^31 - 1)。}sort(a.begin() + 1, a.begin() + 1 + n);//从大到小sort(cha.begin() + 1, cha.begin() + 1 + n);for (int i = 1; i <= n; i++) {sum2 += (long long)a[i] * cha[i];}cout << sum2 - sum1;return 0;
}
前缀和与差分 图文并茂 超详细整理(全网最通俗易懂)-CSDN博客
相关文章:
蓝桥杯备赛-差分-重新排序
问题描述 给定一个数组 AA 和一些查询 Li,RiLi,Ri, 求数组中第 LiLi 至第 RiRi 个元素之和。 小蓝觉得这个问题很无聊, 于是他想重新排列一下数组, 使得最终每个查 询结果的和尽可能地大。小蓝想知道相比原数组, 所有查询结果的总和最多可 以增加多少? 输入格式 输…...
使用DeepSeek+蓝耘快速设计网页简易版《我的世界》小游戏
前言:如今,借助先进的人工智能模型与便捷的云平台,即便是新手开发者,也能开启创意游戏的设计之旅。DeepSeek 作为前沿的人工智能模型,具备强大的功能与潜力,而蓝耘智算云平台则为其提供了稳定高效的运行环境…...
基于Matlab设计GUI图像处理交互界面
Image-Processing-GUI 项目说明 本博文提供了完整的代码和使用教程,适合新入门的朋友参考,完整代码资源文件请转至文末的下载链接。 本项目是《Matlab实践》中图像处理软件题目,本项目实现的具体内容如下 基于Matlab设计GUI交互界面图像的…...
javase集合框架List篇
一、Vector和ArrayList、LinkedList联系和区别,分别的使用场景 ArrayList:底层是数组实现,线程不安全,查询和修改非常快,但是增加和删除慢 LinkedList: 底层是双向链表,线程不安全,查询和修改…...
浙江大学:DeepSeek行业应用案例集(153页)(文末可下载PDF)
浙江大学:DeepSeek行业应用案例集(153页)(文末可下载PDF) 全文链接:浙江大学:DeepSeek行业应用案例集(153页)(文末可下载PDF) | AI探金 全文链接&…...
【 IEEE出版 | 快速稳定EI检索 | 往届已EI检索】2025年储能及能源转换国际学术会议(ESEC 2025)
重要信息 主会官网:www.net-lc.net 【论文【】投稿】 会议时间:2025年5月9-11日 会议地点:中国-杭州 截稿时间:见官网 提交检索:IEEE Xplore, EI Compendex, Scopus 主会NET-LC 2025已进入IEEE 会议官方列表!&am…...
电路原理(电容 集成电路NE555)
电容 1.特性:充放电,隔直流,通交流 2.电容是通过聚集正负电荷来存储电能的 3.电容充放电过程可等效为导通回路 4.多电容并联可以把容量叠加,但是多电容串联就不会,只会叠加电容的耐压值。 6.电容充放电时相当于通路&a…...
记录小白使用 Cursor 开发第一个微信小程序(一):注册账号及下载工具(250308)
文章目录 记录小白使用 Cursor 开发第一个微信小程序(一):注册账号及下载工具(250308)一、微信小程序注册摘要1.1 注册流程要点 二、小程序发布流程三、下载工具 记录小白使用 Cursor 开发第一个微信小程序(…...
哪些业务场景更适合用MongoDB?何时比MySQL/PostgreSQL好用?
哪些业务场景更适合用MongoDB?何时比MySQL/PostgreSQL好用? 就像淘宝的个性化推荐需要灵活调整商品标签,MongoDB这种"变形金刚"式的数据库,在处理以下三类中国特色业务场景时更具优势: 一、动态数据就像&q…...
【从零开始学习计算机科学】计算机组成原理(二)信息表示与编码
【从零开始学习计算机科学】计算机组成原理(二)信息表示与编码 信息表示与编码进位计数制十进制(Decimal)二进制(Binary)十六进制(Hexadecimal)进位计数制之间的转换常用的信息分类与表示定点表示无符号数的编码正整数的表示原码表示法定点小数的原码表示定点整数的原码…...
【从零开始学习计算机科学】操作系统(五)处理器调度
【从零开始学习计算机科学】操作系统(五)处理器调度 处理器调度一些简单的短程调度算法的思路先来先服务(First-Come-First-Served,FCFS)优先级调度及其变种最短作业优先调度算法(SJF)--非抢占式最短作业优先调度算法(SJF)--抢占式最高响应比优先调度算法轮转调度算法…...
Flink之水印(watermark)的补充理解
水印(Watermark):用于事件时间处理,标记数据流的进度,解决乱序和延迟问题,触发窗口计算 一、Flink 水印的作用 处理乱序事件 水印(Watermark)是 Flink 用于处理事件时间&…...
数据结构全解析:从线性到非线性,优缺点与应用场景深度剖析
1. 线性数据结构 (1)数组(Array)(适合静态数据) 优点: 随机访问高效:通过索引可以直接访问元素,时间复杂度为 O(1)。 内存连续:数组在内存中是连续存储的&…...
《使用 Python Flask + MySQL + ECharts 构建销售数据看板》实战案例笔记
《使用 Python Flask + MySQL + ECharts 构建销售数据看板》实战案例笔记 技术栈说明 后端:Python 3.10 + Flask 框架数据库:MySQL前端:ECharts 5.4 + HTML/CSS数据可视化:柱状图 / 折线图 / 饼图 / 雷达图项目结构 project/ ├── server.py # 后端服务 └──…...
StringBuilder和StringJoiner的运用
package test12; import java.util.Scanner; import java.util.StringJoiner;public class Test { public static void main(String[] args) {/* String str "你玩的真好,下次别玩了,TMD,CNM";String[] arr {"TMD", &…...
科技创新:改变生活的力量与未来趋势
人工智能在智能客服中的应用越来越普遍。它改变了传统的客服模式。AI可以快速回答用户的问题,提高了客服效率和服务质量。 首先,人工智能能够处理大量信息。智能客服可以在几秒钟内回应客户的请求。这比人工客服快得多。客户不需要等待很久就能得到答案…...
Maven指定JDK
在使用 Maven 管理 Java 项目时,有时需要指定使用特定的 JDK 版本。这通常是因为项目需要与特定版本的 JDK 兼容,或者在不同的开发环境中需要确保使用正确的 JDK 版本。通常来说在IDEA工具中设置了正确的JDK版本,使用IDEA编译也不会有任何异常…...
Jenkins持续集成与Web前端、SpringBoot项目的部署
Jenkins是一个开源的持续集成(Continuous Integration, CI)和持续交付(Continuous Delivery, CD)工具,广泛应用于软件开发过程中。它基于Java开发,旨在提供一个开放易用的软件平台,帮助软件项…...
如何使用Opentelemetry+jaeger对Go与Java项目实现分布式链路追踪
本文介绍![如何使用Opentelemetryjaeger实现分布式链路追踪] 关于opentelemetry的介绍可以看下面的文章 https://blog.csdn.net/qq_62368250/article/details/143516314本文中相关图片以及源代码地址 https://github.com/wuchenyanghaoshuai/others/blob/main/step39/README.…...
LabVIEW闭环控制系统硬件选型与实时性能
在LabVIEW闭环控制系统的开发中,硬件选型直接影响系统的实时性、精度与稳定性。需综合考虑数据采集速度(采样率、接口带宽)、计算延迟(算法复杂度、处理器性能)、输出响应时间(执行器延迟、控制周期&#x…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
2025年能源电力系统与流体力学国际会议 (EPSFD 2025)
2025年能源电力系统与流体力学国际会议(EPSFD 2025)将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会,EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:
根据万维钢精英日课6的内容,使用AI(2025)可以参考以下方法: 四个洞见 模型已经比人聪明:以ChatGPT o3为代表的AI非常强大,能运用高级理论解释道理、引用最新学术论文,生成对顶尖科学家都有用的…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)
第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10pip3.10) 一:前言二:安装编译依赖二:安装Python3.10三:安装PIP3.10四:安装Paddlepaddle基础框架4.1…...
rm视觉学习1-自瞄部分
首先先感谢中南大学的开源,提供了很全面的思路,减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接:https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架: 代码框架结构:readme有…...
【记录坑点问题】IDEA运行:maven-resources-production:XX: OOM: Java heap space
问题:IDEA出现maven-resources-production:operation-service: java.lang.OutOfMemoryError: Java heap space 解决方案:将编译的堆内存增加一点 位置:设置setting-》构建菜单build-》编译器Complier...
aurora与pcie的数据高速传输
设备:zynq7100; 开发环境:window; vivado版本:2021.1; 引言 之前在前面两章已经介绍了aurora读写DDR,xdma读写ddr实验。这次我们做一个大工程,pc通过pcie传输给fpga,fpga再通过aur…...
