AcWing 106 动态中位数
发布日期:2021-05-28 16:31:15 浏览次数:10 分类:技术文章

本文共 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<
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<

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/88682638 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 107 超快速排序
下一篇:AcWing 105 七夕祭

发表评论

最新留言

不错!
[***.144.177.141]2024年02月10日 02时19分32秒