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系统首页 管理员登录进入师生健康信息管理系统可以查看个人中心、学生管理、教师管理、数据收集管理、问卷分类管理、疫情问卷管理、问卷调查管理…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
