【算法】动态中位数(对顶堆)
题目
依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。
输入格式
第一行输入一个整数 P,代表后面数据集的个数,接下来若干行输入各个数据集。
每个数据集的第一行首先输入一个代表数据集的编号的整数。
然后输入一个整数 M,代表数据集中包含数据的个数,M 一定为奇数,数据之间用空格隔开。
数据集的剩余行由数据集的数据构成,每行包含 10 个数据,最后一行数据量可能少于 10 个,数据之间用空格隔开。
输出格式
对于每个数据集,第一行输出两个整数,分别代表数据集的编号以及输出中位数的个数(应为数据个数加一的二分之一),数据之间用空格隔开。
数据集的剩余行由输出的中位数构成,每行包含 10 个数据,最后一行数据量可能少于 10 个,数据之间用空格隔开。
输出中不应该存在空行。
数据范围
1≤P≤1000
1≤M≤99999
所有 M 相加之和不超过 5×1e5
输入样例:
3
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56
输出样例:
1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3
-7 -3
思路
使用一个大根堆一个小根堆动态维护一个对顶堆,保持在放入奇数个数据时,下面的堆比上面的堆多1个元素,如下图所示。

当总元素个数为奇数的时候,输出down.top(),即为当前所有元素的中位数。
代码
#include<bits/stdc++.h>
using namespace std;void solve()
{int n,m;cin >> n >> m;cout << n << " " << (m + 1) / 2 << endl;priority_queue<int, vector<int>,less<>> down;priority_queue<int, vector<int>,greater<>> up;int cnt = 0;for(int i = 1; i <= m; i ++){int x;cin >> x;if(down.empty() || x <= down.top()) down.push(x);else up.push(x);if(down.size() > up.size() + 1) up.push(down.top()),down.pop();if(up.size() > down.size()) down.push(up.top()),up.pop();if(i % 2){cout << down.top() << " ";if(++ cnt % 10 == 0) cout << endl;}}if(cnt % 10) cout << endl;
}int main()
{int T;cin >> T;while(T --)solve();return 0;
}
| 难度:中等 |
| 时/空限制:2s / 256MB |
| 总通过数:9036 |
| 总尝试数:22991 |
| 来源:《算法竞赛进阶指南》 |
| 算法标签 堆 |
题目来自: 106. 动态中位数 - AcWing题库
相关文章:
【算法】动态中位数(对顶堆)
题目 依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。 输入格式 第一行输入一个整数 P,代表后面数据集的个数,接下来若干行输入各个数据集。 每个数据集的第一行首先输入一个代表…...
mysql服务多实例运行
1、官网下载mysql安装包 https://downloads.mysql.com/archives/community/ 2、解压安装包 tar -zxvf mysql-8.1.0-linux-glibc2.28-aarch64.tar.xz -C /usr/localmv /usr/local/mysql-8.1.0-linux-glibc2.28-aarch64 /usr/local/mysql 3、创建mysql用户组 groupadd…...
「HDLBits题解」Module fadd
本专栏的目的是分享可以通过HDLBits仿真的Verilog代码 以提供参考 各位可同时参考我的代码和官方题解代码 或许会有所收益 题目链接:Module fadd - HDLBits module top_module (input [31:0] a,input [31:0] b,output [31:0] sum );//wire [15:0] t1, t2 ; wire co…...
微软等开源评估ChatGPT、Phi、Llma等,统一测试平台
微软亚洲研究院、中国科学院自动化研究所、中国科学技术大学和卡内基梅隆大学联合开源了,用于评估、分析大语言模型的统一测试平台——PromptBench。 Prompt Bench支持目前主流的开源、闭源大语言模型,例如,ChatGPT、GPT-4、Phi、Llma1/2、G…...
DDNS-GO配置使用教程
环境:openwrt 下载地址:Releases jeessy2/ddns-go GitHub 下载 ssh至openwrt根目录,根据你的处理器选择要下载的版本,我是路由器,选择的是 ddns-go_5.7.1_linux_arm64.tar.gz wget github链接 安装 tar -zxvf…...
flex弹性盒子常用的布局属性详解
想必大家在开发中经常会用到flex布局。而且还会经常用到 justify-content 属性实现分栏等等 接下来给大家分别讲一下 justify-content 的属性值。 以下是我敲的效果图大家可以清晰看出区别 space-between 属性值可以就是说两端对齐 space-evenly 属性值是每个盒子之间的…...
2023年Gartner® DevOps平台魔力象限发布,Atlassian被评为“领导者”
Atlassian在2023年Gartner魔力象限的DevOps平台评选中,被评为领导者。 Gartner根据执行能力和愿景的完整性,对全球14家DevOps平台提供商进行了评估,并发布2023年Gartner魔力象限。其中,Atlassian被评为领导者。 Atlassian提供了一…...
kylin集群使用nginx反向代理
前文已经提到,我安装了kylin集群。 kylin3集群问题和思考(单机转集群)-CSDN博客文章浏览阅读151次,点赞3次,收藏6次。由于是同一个集群的,元数据没有变化,所以,直接将原本的kylin使用…...
小红书搜索团队提出全新框架:验证负样本对大模型蒸馏的价值
大语言模型(LLMs)在各种推理任务上表现优异,但其黑盒属性和庞大参数量阻碍了它在实践中的广泛应用。特别是在处理复杂的数学问题时,LLMs 有时会产生错误的推理链。传统研究方法仅从正样本中迁移知识,而忽略了那些带有错…...
汽车销售领域相关专业术语
引言 本文是笔者在从事汽车销售领域信息化建设过程,积累的一些专业术语注解,供诸位参考交流。 专业术语清单 4S店 汽车销售服务4S店;是由经销商投资建设,按照汽车生产厂家规定的标准建造,是一种集整车销售(Sale)、零配件(Sparepart)、售后服务(Service)、信息…...
代币合约 ERC20 Token接口
代币合约 在以太坊上发布代币就要遵守以太坊的规则,那么以太坊有什么规则呢?以太坊的精髓就是利用代码规定如何运作,由于在以太坊上发布智能合约是不能修改和删除的,所以智能合约一旦发布,就意味着永久有效,不可篡改…...
判断回文字符串—C语言
题目要求 输入一个字符串,判断该字符串是否为回文。回文就是字符串中心对称,从左向右读和从右向左读的内容是一样的。 输入格式: 输入在一行中给出一个不超过80个字符长度的、以回车结束的非空字符串。 输出格式: 输出在第1行中…...
如何在Docker本地搭建流程图绘制神器draw.io并实现公网远程访问
推荐 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站 前言 提到流程图,大家第一时间可能会想到Visio,不可否认,VIsio确实是功能强大,但是软…...
Web前端篇——el-timeline+el-scrollbar时间轴数据刷新后自动显示滚动条
背景:使用el-timelineel-scrollbar显示时间轴,当时间轴数据刷新时,el-scrollbar滚动条会自动隐藏。 当给el-scrollbar设置了永久显示滚动条(如下代码),以为可以一劳永逸,发现问题仍然存在。 .…...
Flutter 监听前台和后台切换的状态
一 前后台的切换状态监听 混入 WidgetsBindingObserver 这个类,这里提供提供了程序状态的一些监听 二 添加监听和销毁监听 overridevoid initState() {super.initState();//2.页面初始化的时候,添加一个状态的监听者WidgetsBinding.instance.addObserver…...
图解Kubernetes的服务(Service)
pod 准备: 不要直接使用和管理Pods: 当使用ReplicaSet水平扩展scale时,Pods可能被terminated当使用Deployment时,去更新Docker Image Version,旧Pods会被terminated,然后创建新Pods 0 啥是服务…...
facebook广告素材制作要注意哪些
在制作Facebook广告素材时,需要注意以下几点: 目标受众:了解目标受众的喜好、需求和兴趣,以便制作能够吸引他们的广告素材。广告格式:选择适合广告内容的格式,如图片、视频、幻灯片等。同时,要…...
Android 应用流量监控实践
背景 得物Apm系统本身包含网络接口性能监控的能力,但接口监控主要关注的是接口的耗时、异常率等信息,没有流量消耗相关维度的统计信息,并且一部分流量消耗可能来自于音视频等其他特殊场景,在接口监控的盲区外。 为了了解用户目前…...
并发前置知识一:线程基础
一、通用的线程生命周期:“五态模型” 二、java线程有哪几种状态? New:创建完线程Runable:start(),这里的Runnable包含操作的系统的Running(运行状态)和Ready(上面的可运行状态)Blo…...
计算机网络 物理层
文章目录 物理层物理层的基本概念数据通信的基础知识数据通信系统的模型有关信道的几个基本概念信道的极限容量 物理层下面的传输媒体导引型传输媒体非引导型传输媒体 信道复用技术波分复用码的复用 宽带接入技术ADSL 技术光纤同轴混合网 (HFC 网)FTTx 技术 物理层 …...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)
前言: 最近在做行为检测相关的模型,用的是时空图卷积网络(STGCN),但原有kinetic-400数据集数据质量较低,需要进行细粒度的标注,同时粗略搜了下已有开源工具基本都集中于图像分割这块,…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
