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系统首页 管理员登录进入师生健康信息管理系统可以查看个人中心、学生管理、教师管理、数据收集管理、问卷分类管理、疫情问卷管理、问卷调查管理…...
智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
【Linux系统】Linux环境变量:系统配置的隐形指挥官
。# Linux系列 文章目录 前言一、环境变量的概念二、常见的环境变量三、环境变量特点及其相关指令3.1 环境变量的全局性3.2、环境变量的生命周期 四、环境变量的组织方式五、C语言对环境变量的操作5.1 设置环境变量:setenv5.2 删除环境变量:unsetenv5.3 遍历所有环境…...
Web后端基础(基础知识)
BS架构:Browser/Server,浏览器/服务器架构模式。客户端只需要浏览器,应用程序的逻辑和数据都存储在服务端。 优点:维护方便缺点:体验一般 CS架构:Client/Server,客户端/服务器架构模式。需要单独…...
