当前位置: 首页 > news >正文

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个正整数作成的一个数列&#xff0c;进行如下操作&#xff1a;每一次擦去其中的两个数a和b&#xff0c;然后在数列中加入一个数a*b1&#xff0c;如此下去直至黑板上剩下一个数&#xff0c;在所有按这种操作方式最后得…...

代码随想录算法训练营第二十七天 | 93.复原IP地址,78.子集,90.子集II

一、参考资料复原IP地址题目链接/文章讲解&#xff1a;https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html 视频讲解&#xff1a;https://www.bilibili.com/video/BV1XP4y1U73i/子集题目链接/文章讲解&#xff1a;https://programmercarl.com/0078.…...

jvm类加载器

概念 Bootstarp ClassLoader (引导类加载器) 加载String等核心的类Ext ClassLoader (拓展类加载器)System ClassLoader (系统类加载器) 加载用户自定义的类 关系 BootstrapClassLoader 包含 ExtClassLoaderExtClassLoader 包含 SystemClassLoader彼此是包含关系&#xff0c;不…...

Rust学习入门--【7】Rust 数据类型

类型系统 对于任何一门语言都是重中之重&#xff0c;因为它体现了语言所支持的不同类型的值。 类型系统 也是 IT 初学者最难啃的三座大山之一&#xff0c;而类型系统之所以难以理解&#xff0c;主要是没有合适的现成的参考体系。 我们说类型系统 存在的目的&#xff0c;就是 …...

阅读MySQL必知必会,查缺补漏

MySQL自带数据库 information_schema&#xff1a;是MySQL自带的数据库&#xff0c;主要保持MySQL数据库服务器的系统信息&#xff0c;比如数据库的名称&#xff0c;数据库表的名称&#xff0c;字段名称&#xff0c;存储权限等。 performance_schema&#xff1a;是MySQL系统自…...

MySQL数据库10——多表连接查询

数据如果在多个表里面&#xff0c;需要进行连接查询。 一般在pandas里面merge合并会用到一个索引&#xff0c;按这个索引的规则进行合并叫做有规则的等值连接。若不按规则连接&#xff0c;遍历两两组合的所有可能性&#xff0c;叫做笛卡尔积。 笛卡尔积连接 通常人们都会设置…...

华为OD机试 - 括号检查(Python)| 真题含思路

括号检查 题目 现有一字符串 仅由 (,),{,},[,] 六种括号组成,若字符串满足以下条件之一,则为无效字符串 任意类型的左右括号数量不相等 存在未按正确顺序(先左后右)闭合的括号, 输出括号的最大嵌套深度 若字符串无效则输出 0 0 <= 字符串长度 <= 100000 输入 一个只…...

安全渗透测试中的一款免费开源的超级关键词URL采集工具

安全渗透测试中的一款免费开源的超级关键词URL采集工具。 #################### 免责声明&#xff1a;工具本身并无好坏&#xff0c;希望大家以遵守《网络安全法》相关法律为前提来使用该工具&#xff0c;支持研究学习&#xff0c;切勿用于非法犯罪活动&#xff0c;对于恶意使…...

数据资产管理实践白皮书(6.0版)解读

目录 第一章数据资产管理概述 ( 一 ) 数据资产管理和数据要素的关系...

c/c++开发,无可避免的函数指针使用案例

一、函数指针简介 函数指针是指指向函数而非指向对象的指针。像其他指针一样&#xff0c;函数指针也指向某个特定的类型。函数类型由其返回类型以及形参表确定&#xff0c;而与函数名无关。例如&#xff1a; char* (*pf1)(char * p1,char *p2); 这是一个函数指针&#xff0c;其…...

QT(12)-QThreadPool

1 简介 QThreadPool是Qt框架中的一个类&#xff0c;提供了一组工作线程池。该线程池自动管理一组工作线程&#xff0c;在线程可用时分配任务。使用线程池的主要优点是&#xff0c;它可以减少创建和销毁线程的开销&#xff0c;因为可以重复使用线程。 线程池设计用于场景中&am…...

【Java|golang】1138. 字母板上的路径

我们从一块字母板上的位置 (0, 0) 出发&#xff0c;该坐标对应的字符为 board[0][0]。 在本题里&#xff0c;字母板为board [“abcde”, “fghij”, “klmno”, “pqrst”, “uvwxy”, “z”]&#xff0c;如下所示。 我们可以按下面的指令规则行动&#xff1a; 如果方格存…...

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( ) 进行任务的创建的时候&#xff0c;会初始化任务的堆栈、保存cpu的寄存器、创建任务的控制块&#xff08;OS_TCB&#xff09;等的操作&#xff1b; if (OSTCBPrioTbl[prio] (OS_…...

Solon2 开发之容器,七、切面与函数环绕拦截

想要环绕拦截一个 Bean 的函数。需要三个前置条件&#xff1a; 通过注解做为“切点”&#xff0c;进行拦截&#xff08;不能无缘无故给拦了吧&#xff1f;费性能&#xff09;Bean 的 method 是被代理的在 Bean 被扫描之前&#xff0c;完成环绕拦截的注册 1、定义切点和注册环…...

代码随想录第十天(28)

文章目录28. 找出字符串中第一个匹配项的下标看答案KMPnext数组&#xff08;前缀表&#xff09;最长公共前后缀如何计算前缀表前缀表与next数组时间复杂度分析28. 找出字符串中第一个匹配项的下标 莫得思路……好久没做题&#xff0c;都已经忘得差不多了 看答案 其实就是自己…...

循环队列来了解一下!!

笔者在之前的一篇文章&#xff0c;详细的介绍了&#xff1a;队列之单向链表与双向链表的模拟实现&#xff1a;https://blog.csdn.net/weixin_64308540/article/details/128742090?spm1001.2014.3001.5502 感兴趣的各位老铁&#xff0c;可以参考一下啦&#xff01;下面进入循环…...

Idea打包springboot项目war包,测试通过

pom.xml文件 <!--包名以及版本号&#xff0c;这个是打包时候使用&#xff0c;版本可写可不写&#xff0c;建议写有利于维护系统--> <artifactId>tsgdemo</artifactId> <version>0.0.1-SNAPSHOT</version> <!--打包形式--> <packaging&…...

python+django高校师生健康信息管理系统pycharm

管理员功能模块 4.1登录页面 管理员登录&#xff0c;通过填写注册时输入的用户名、密码、角色进行登录&#xff0c;如图所示。 4.2系统首页 管理员登录进入师生健康信息管理系统可以查看个人中心、学生管理、教师管理、数据收集管理、问卷分类管理、疫情问卷管理、问卷调查管理…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

ssc377d修改flash分区大小

1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...