当前位置: 首页 > 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题库

http://www.lryc.cn/news/278813.html

相关文章:

  • mysql服务多实例运行
  • 「HDLBits题解」Module fadd
  • 微软等开源评估ChatGPT、Phi、Llma等,统一测试平台
  • DDNS-GO配置使用教程
  • flex弹性盒子常用的布局属性详解
  • 2023年Gartner® DevOps平台魔力象限发布,Atlassian被评为“领导者”
  • kylin集群使用nginx反向代理
  • 小红书搜索团队提出全新框架:验证负样本对大模型蒸馏的价值
  • 汽车销售领域相关专业术语
  • 代币合约 ERC20 Token接口
  • 判断回文字符串—C语言
  • 如何在Docker本地搭建流程图绘制神器draw.io并实现公网远程访问
  • Web前端篇——el-timeline+el-scrollbar时间轴数据刷新后自动显示滚动条
  • Flutter 监听前台和后台切换的状态
  • 图解Kubernetes的服务(Service)
  • facebook广告素材制作要注意哪些
  • Android 应用流量监控实践
  • 并发前置知识一:线程基础
  • 计算机网络 物理层
  • 浅谈轻量级Kubernetes—K3s
  • Web APIs知识点讲解
  • Python商业数据挖掘实战——爬取网页并将其转为Markdown
  • 初识 Elasticsearch 应用知识,一文读懂 Elasticsearch 知识文集(1)
  • StampedLock详解
  • Linux中DCHP与时间同步
  • 国产系统-银河麒麟桌面版V10安装字体-wps安装字体
  • python 10常用自动化脚本收藏好
  • java物品检验管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目
  • Pandas实战100例 | 案例 2: 数据探索 - 查看和理解数据
  • c++qt-基本组件