1555数列极差(队列 优先队列 )
目录
题目描述
解题思路
代码部分
题目描述
在黑板上写了N个正整数作成的一个数列,进行如下操作:每一次擦去其中的两个数a和b,然后在数列中加入一个数a*b+1,如此下去直至黑板上剩下一个数,在所有按这种操作方式最后得到的数中,最大的max,最小的为min,则该数列的极差定义为M=max-min。
输入
第一行,一个数为N;
第二行,N个数。
输出
输出极差。
样例输入
3
1 2 3
样例输出
2
解题思路
经过计算可以证明:
当输入的一行数按升序排列时,最终算出的结果值最大;
当输入的一行数按降序排列时,最终算出的结果值最小。(解题关键)
可以采用优先队列解题,最终队列剩下的那个值就是这一行数最终算出来的结果。
升序和降序队列的计算可以双线同时进行。
升序优先队列的解决方法:
默认的优先队列是降序排列的优先队列,如何能让降序队列变成升序队列呢?有一个简单方法:
将降序队列的所有数变成原来的相反数,再用“优先队列”存储,得到的队列和原队列正好相反,
原来的队列是降序队列,现在的队列就成功转化成了升序队列!
转化成升序队列之后一定要时刻注意,不能直接调用升序队列存储的数据!因为升序队列存储的数据是原数据的相反数。同时,继续向升序队列队尾push值的时候,一定要先变成相反数再推入!!
代码部分
#include <iostream>
#include <cstring>
#include <queue>
typedef long long ll;
using namespace std;
priority_queue<ll>down;//降序
priority_queue<ll>up;//升序
ll x, y;
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> x;down.push(x);//降序up.push(-x);//升序。//默认的优先队列按照降序存储,//所以如果想要实现升序存储,只能存入-x;}for (int i = 1; i < n; i++){//处理降序队列的问题x = down.top(); down.pop();y = down.top(); down.pop();down.push(x * y + 1);//处理升序队列的问题x = -up.top(); up.pop();//因为在实现升序存储时将存入的数据变成了相反数,//所以这里调用真实数据时必须再取一次相反数y = -up.top(); up.pop();up.push(-(x * y + 1));//x*y=(-x)*(-y)//这里一定要注意!!!//别忘了实现升序排列要将数据变成相反数存储!!!//一定是-(x*y+1)!!!}cout << -up.top() - down.top();//up.top()是原本数据的相反数,最后这里也要变回来return 0;
}
相关文章:
1555数列极差(队列 优先队列 )
目录 题目描述 解题思路 代码部分 题目描述 在黑板上写了N个正整数作成的一个数列,进行如下操作:每一次擦去其中的两个数a和b,然后在数列中加入一个数a*b1,如此下去直至黑板上剩下一个数,在所有按这种操作方式最后得…...
代码随想录算法训练营第二十七天 | 93.复原IP地址,78.子集,90.子集II
一、参考资料复原IP地址题目链接/文章讲解:https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html 视频讲解:https://www.bilibili.com/video/BV1XP4y1U73i/子集题目链接/文章讲解:https://programmercarl.com/0078.…...
jvm类加载器
概念 Bootstarp ClassLoader (引导类加载器) 加载String等核心的类Ext ClassLoader (拓展类加载器)System ClassLoader (系统类加载器) 加载用户自定义的类 关系 BootstrapClassLoader 包含 ExtClassLoaderExtClassLoader 包含 SystemClassLoader彼此是包含关系,不…...
Rust学习入门--【7】Rust 数据类型
类型系统 对于任何一门语言都是重中之重,因为它体现了语言所支持的不同类型的值。 类型系统 也是 IT 初学者最难啃的三座大山之一,而类型系统之所以难以理解,主要是没有合适的现成的参考体系。 我们说类型系统 存在的目的,就是 …...
阅读MySQL必知必会,查缺补漏
MySQL自带数据库 information_schema:是MySQL自带的数据库,主要保持MySQL数据库服务器的系统信息,比如数据库的名称,数据库表的名称,字段名称,存储权限等。 performance_schema:是MySQL系统自…...
MySQL数据库10——多表连接查询
数据如果在多个表里面,需要进行连接查询。 一般在pandas里面merge合并会用到一个索引,按这个索引的规则进行合并叫做有规则的等值连接。若不按规则连接,遍历两两组合的所有可能性,叫做笛卡尔积。 笛卡尔积连接 通常人们都会设置…...
华为OD机试 - 括号检查(Python)| 真题含思路
括号检查 题目 现有一字符串 仅由 (,),{,},[,] 六种括号组成,若字符串满足以下条件之一,则为无效字符串 任意类型的左右括号数量不相等 存在未按正确顺序(先左后右)闭合的括号, 输出括号的最大嵌套深度 若字符串无效则输出 0 0 <= 字符串长度 <= 100000 输入 一个只…...
安全渗透测试中的一款免费开源的超级关键词URL采集工具
安全渗透测试中的一款免费开源的超级关键词URL采集工具。 #################### 免责声明:工具本身并无好坏,希望大家以遵守《网络安全法》相关法律为前提来使用该工具,支持研究学习,切勿用于非法犯罪活动,对于恶意使…...
数据资产管理实践白皮书(6.0版)解读
目录 第一章数据资产管理概述 ( 一 ) 数据资产管理和数据要素的关系...
c/c++开发,无可避免的函数指针使用案例
一、函数指针简介 函数指针是指指向函数而非指向对象的指针。像其他指针一样,函数指针也指向某个特定的类型。函数类型由其返回类型以及形参表确定,而与函数名无关。例如: char* (*pf1)(char * p1,char *p2); 这是一个函数指针,其…...
QT(12)-QThreadPool
1 简介 QThreadPool是Qt框架中的一个类,提供了一组工作线程池。该线程池自动管理一组工作线程,在线程可用时分配任务。使用线程池的主要优点是,它可以减少创建和销毁线程的开销,因为可以重复使用线程。 线程池设计用于场景中&am…...
【Java|golang】1138. 字母板上的路径
我们从一块字母板上的位置 (0, 0) 出发,该坐标对应的字符为 board[0][0]。 在本题里,字母板为board [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”],如下所示。 我们可以按下面的指令规则行动: 如果方格存…...
Flink 1.14从简单到源码第三讲
文章目录 1.flink多流操作Api1.1split 分流操作1.2.侧输出流1.3.connect 连接操作1.4.union 操作1.5 coGroup 协同分组1.6 join1.7 broadcast 广播2.process3.并行度和Api3.1 任务提交简单流程3.2 task与算子链4. Flink 时间相关(窗口计算)4.1时间语义(窗口计算)4.2 新版api指定…...
淘宝API接口系列,获取购买到的商品订单列表,卖出的商品订单列表,订单详情,订单物流,买家信息,收货地址列表,买家token
custom自定义API操作buyer_order_list获取购买到的商品订单列表buyer_order_detail获取购买到的商品订单详情buyer_order_express获取购买到的商品订单物流buyer_address_list收货地址列表buyer_address_add添加收货地址buyer_info买家信息buyer_token买家tokenseller_order_li…...
ucos-ii 的任务调度原理和实现
ucosii 任务调度和原理1、ucos-ii 任务创建与任务调度 1.1、任务的创建 当你调用 OSTaskCreate( ) 进行任务的创建的时候,会初始化任务的堆栈、保存cpu的寄存器、创建任务的控制块(OS_TCB)等的操作; if (OSTCBPrioTbl[prio] (OS_…...
Solon2 开发之容器,七、切面与函数环绕拦截
想要环绕拦截一个 Bean 的函数。需要三个前置条件: 通过注解做为“切点”,进行拦截(不能无缘无故给拦了吧?费性能)Bean 的 method 是被代理的在 Bean 被扫描之前,完成环绕拦截的注册 1、定义切点和注册环…...
代码随想录第十天(28)
文章目录28. 找出字符串中第一个匹配项的下标看答案KMPnext数组(前缀表)最长公共前后缀如何计算前缀表前缀表与next数组时间复杂度分析28. 找出字符串中第一个匹配项的下标 莫得思路……好久没做题,都已经忘得差不多了 看答案 其实就是自己…...
循环队列来了解一下!!
笔者在之前的一篇文章,详细的介绍了:队列之单向链表与双向链表的模拟实现:https://blog.csdn.net/weixin_64308540/article/details/128742090?spm1001.2014.3001.5502 感兴趣的各位老铁,可以参考一下啦!下面进入循环…...
Idea打包springboot项目war包,测试通过
pom.xml文件 <!--包名以及版本号,这个是打包时候使用,版本可写可不写,建议写有利于维护系统--> <artifactId>tsgdemo</artifactId> <version>0.0.1-SNAPSHOT</version> <!--打包形式--> <packaging&…...
python+django高校师生健康信息管理系统pycharm
管理员功能模块 4.1登录页面 管理员登录,通过填写注册时输入的用户名、密码、角色进行登录,如图所示。 4.2系统首页 管理员登录进入师生健康信息管理系统可以查看个人中心、学生管理、教师管理、数据收集管理、问卷分类管理、疫情问卷管理、问卷调查管理…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...
鸿蒙HarmonyOS 5军旗小游戏实现指南
1. 项目概述 本军旗小游戏基于鸿蒙HarmonyOS 5开发,采用DevEco Studio实现,包含完整的游戏逻辑和UI界面。 2. 项目结构 /src/main/java/com/example/militarychess/├── MainAbilitySlice.java // 主界面├── GameView.java // 游戏核…...
