
AcWing 106 动态中位数
ma; priority_queue ,greater > mi; for(int i = 1;i <= n;i++){ cin>>a; ma.push(a); if(mi.size() && mi.top() < ma.top()){ int x = ma.top(),y = mi.top(); ma.pop(),mi.pop(); ma.push(y),mi.push(x); } if(ma.size() == mi.size() + 2){ int x = ma.top(); mi.push(x); ma.pop(); } if(i % 2 == 1) cout< <<" "; if((i + 1) % 20 == 0) cout<
发布日期:2021-05-28 16:31:15
浏览次数:29
分类:技术文章
本文共 1275 字,大约阅读时间需要 4 分钟。
题目描述:
依次读入一个整数序列,每当已经读入的整数个数为奇数时,输出已读入的整数构成的序列的中位数。
输入格式
第一行输入一个整数P,代表后面数据集的个数,接下来若干行输入各个数据集。每个数据集的第一行首先输入一个代表数据集的编号的整数。然后输入一个整数M,代表数据集中包含数据的个数,M一定为奇数,数据之间用空格隔开。
数据集的剩余行由数据集的数据构成,每行包含10个数据,最后一行数据量可能少于10个,数据之间用空格隔开。
输出格式
对于每个数据集,第一行输出两个整数,分别代表数据集的编号以及输出中位数的个数(应为数据个数加一的二分之一),数据之间用空格隔开。数据集的剩余行由输出的中位数构成,每行包含10个数据,最后一行数据量可能少于10个,数据之间用空格隔开。输出中不应该存在空行。
数据范围
1≤P≤1000,
1≤M≤9999输入样例:
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 51 2 3 4 52 59 8 7 6 53 1223 23 22 22 13 3 5 5 3 -3 -7 -3
分析:
本题与基本相同。
维护一个对顶堆,即一个大根堆和一个小根堆,大根堆里存储较小的一半数据,小根堆里存储较大的一半数据。读入数据先存入大根堆,如果小根堆不为空且小根堆堆顶小于大根堆堆顶则交换两个堆顶元素,如果小根堆元素个数比大根堆元素个数少了2,则将大根堆堆顶元素插入到小根堆中。每次查询中位数输出大根堆堆顶即可。
#include#include #include using namespace std;const int maxn = 10005;int p,m,n,a;int main(){ cin>>p; while(p--){ cin>>m>>n; cout< <<" "<<(n + 1) / 2<
转载地址:https://blog.csdn.net/qq_30277239/article/details/88682638 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2025年02月02日 12时06分46秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
vue响应式原理
2019-06-30
flask入门3-表单
2019-06-30
从零学习游戏服务器开发(二) 最后一战概况
2019-06-30
Vue基础
2019-06-30
Koa2微信公众号开发(一) 本地开发调试环境搭建
2019-06-30
惊奇!用Java也能实现比特币系统
2019-06-30
MongoDB ( 二 )Update修改器
2019-06-30
高收入的背后,码农的亚健康问题也不容忽视
2019-06-30
CAS SSO单点登录框架学习
2019-06-30
前端工具
2019-06-30
我在 ClojureScript 的 2017
2019-06-30
vue-xlsx-table: 在浏览器中查看xlsx或xls表格
2019-06-30
mobile-pull-to-refresh: 移动端下拉刷新控件
2019-06-30
【Android】 RecyclerView添加item时数据全部重复
2019-06-30
设计无限滚动下拉加载,实践高性能页面真谛
2019-06-30
webpack2正式优化版,简化操作
2019-06-30
vue.js element-ui 高德地图 选取坐标 dialog
2019-06-30
More than React(二)组件对复用性有害?
2019-06-30
健壮性V.S.准确率——18个深度图像分类模型的健壮性综述
2019-06-30
Creating Great Teams作者问答
2019-06-30