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

【算法】动态中位数(对顶堆)

题目 

依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。

输入格式

第一行输入一个整数 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
来源:《算法竞赛进阶指南》
算法标签

icon-default.png?t=N7T8https://www.acwing.com/problem/search/1/?search_content=%E5%A0%86

题目来自: 106. 动态中位数 - AcWing题库

相关文章:

【算法】动态中位数(对顶堆)

题目 依次读入一个整数序列&#xff0c;每当已经读入的整数个数为奇数时&#xff0c;输出已读入的整数构成的序列的中位数。 输入格式 第一行输入一个整数 P&#xff0c;代表后面数据集的个数&#xff0c;接下来若干行输入各个数据集。 每个数据集的第一行首先输入一个代表…...

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代码 以提供参考 各位可同时参考我的代码和官方题解代码 或许会有所收益 题目链接&#xff1a;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等,统一测试平台

微软亚洲研究院、中国科学院自动化研究所、中国科学技术大学和卡内基梅隆大学联合开源了&#xff0c;用于评估、分析大语言模型的统一测试平台——PromptBench。 Prompt Bench支持目前主流的开源、闭源大语言模型&#xff0c;例如&#xff0c;ChatGPT、GPT-4、Phi、Llma1/2、G…...

DDNS-GO配置使用教程

环境&#xff1a;openwrt 下载地址&#xff1a;Releases jeessy2/ddns-go GitHub 下载 ssh至openwrt根目录&#xff0c;根据你的处理器选择要下载的版本&#xff0c;我是路由器&#xff0c;选择的是 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平台评选中&#xff0c;被评为领导者。 Gartner根据执行能力和愿景的完整性&#xff0c;对全球14家DevOps平台提供商进行了评估&#xff0c;并发布2023年Gartner魔力象限。其中&#xff0c;Atlassian被评为领导者。 Atlassian提供了一…...

kylin集群使用nginx反向代理

前文已经提到&#xff0c;我安装了kylin集群。 kylin3集群问题和思考&#xff08;单机转集群&#xff09;-CSDN博客文章浏览阅读151次&#xff0c;点赞3次&#xff0c;收藏6次。由于是同一个集群的&#xff0c;元数据没有变化&#xff0c;所以&#xff0c;直接将原本的kylin使用…...

小红书搜索团队提出全新框架:验证负样本对大模型蒸馏的价值

大语言模型&#xff08;LLMs&#xff09;在各种推理任务上表现优异&#xff0c;但其黑盒属性和庞大参数量阻碍了它在实践中的广泛应用。特别是在处理复杂的数学问题时&#xff0c;LLMs 有时会产生错误的推理链。传统研究方法仅从正样本中迁移知识&#xff0c;而忽略了那些带有错…...

汽车销售领域相关专业术语

引言 本文是笔者在从事汽车销售领域信息化建设过程,积累的一些专业术语注解,供诸位参考交流。 专业术语清单 4S店   汽车销售服务4S店;是由经销商投资建设,按照汽车生产厂家规定的标准建造,是一种集整车销售(Sale)、零配件(Sparepart)、售后服务(Service)、信息…...

代币合约 ERC20 Token接口

代币合约 在以太坊上发布代币就要遵守以太坊的规则&#xff0c;那么以太坊有什么规则呢?以太坊的精髓就是利用代码规定如何运作&#xff0c;由于在以太坊上发布智能合约是不能修改和删除的&#xff0c;所以智能合约一旦发布&#xff0c;就意味着永久有效&#xff0c;不可篡改…...

判断回文字符串—C语言

题目要求 输入一个字符串&#xff0c;判断该字符串是否为回文。回文就是字符串中心对称&#xff0c;从左向右读和从右向左读的内容是一样的。 输入格式&#xff1a; 输入在一行中给出一个不超过80个字符长度的、以回车结束的非空字符串。 输出格式&#xff1a; 输出在第1行中…...

如何在Docker本地搭建流程图绘制神器draw.io并实现公网远程访问

推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站 前言 提到流程图&#xff0c;大家第一时间可能会想到Visio&#xff0c;不可否认&#xff0c;VIsio确实是功能强大&#xff0c;但是软…...

Web前端篇——el-timeline+el-scrollbar时间轴数据刷新后自动显示滚动条

背景&#xff1a;使用el-timelineel-scrollbar显示时间轴&#xff0c;当时间轴数据刷新时&#xff0c;el-scrollbar滚动条会自动隐藏。 当给el-scrollbar设置了永久显示滚动条&#xff08;如下代码&#xff09;&#xff0c;以为可以一劳永逸&#xff0c;发现问题仍然存在。 .…...

Flutter 监听前台和后台切换的状态

一 前后台的切换状态监听 混入 WidgetsBindingObserver 这个类&#xff0c;这里提供提供了程序状态的一些监听 二 添加监听和销毁监听 overridevoid initState() {super.initState();//2.页面初始化的时候&#xff0c;添加一个状态的监听者WidgetsBinding.instance.addObserver…...

图解Kubernetes的服务(Service)

pod 准备&#xff1a; 不要直接使用和管理Pods&#xff1a; 当使用ReplicaSet水平扩展scale时&#xff0c;Pods可能被terminated当使用Deployment时&#xff0c;去更新Docker Image Version&#xff0c;旧Pods会被terminated&#xff0c;然后创建新Pods 0 啥是服务&#xf…...

facebook广告素材制作要注意哪些

在制作Facebook广告素材时&#xff0c;需要注意以下几点&#xff1a; 目标受众&#xff1a;了解目标受众的喜好、需求和兴趣&#xff0c;以便制作能够吸引他们的广告素材。广告格式&#xff1a;选择适合广告内容的格式&#xff0c;如图片、视频、幻灯片等。同时&#xff0c;要…...

Android 应用流量监控实践

背景 得物Apm系统本身包含网络接口性能监控的能力&#xff0c;但接口监控主要关注的是接口的耗时、异常率等信息&#xff0c;没有流量消耗相关维度的统计信息&#xff0c;并且一部分流量消耗可能来自于音视频等其他特殊场景&#xff0c;在接口监控的盲区外。 为了了解用户目前…...

并发前置知识一:线程基础

一、通用的线程生命周期&#xff1a;“五态模型” 二、java线程有哪几种状态&#xff1f; New&#xff1a;创建完线程Runable&#xff1a;start(),这里的Runnable包含操作的系统的Running&#xff08;运行状态&#xff09;和Ready&#xff08;上面的可运行状态&#xff09;Blo…...

计算机网络 物理层

文章目录 物理层物理层的基本概念数据通信的基础知识数据通信系统的模型有关信道的几个基本概念信道的极限容量 物理层下面的传输媒体导引型传输媒体非引导型传输媒体 信道复用技术波分复用码的复用 宽带接入技术ADSL 技术光纤同轴混合网 (HFC 网&#xff09;FTTx 技术 物理层 …...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...