当前位置:网站首页>POJ - 3784 Running Median(对顶堆)
POJ - 3784 Running Median(对顶堆)
2022-07-07 05:27:00 【WA_自动机】
POJ - 3784 Running Median(对顶堆)
Description
For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After each odd-indexed value is read, output the median (middle value) of the elements received so far.
Input
The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by an odd decimal integer M, (1 ≤ M ≤ 9999), giving the total number of signed integers to be processed. The remaining line(s) in the dataset consists of the values, 10 per line, separated by a single space. The last line in the dataset may contain less than 10 values.
Output
For each data set the first line of output contains the data set number, a single space and the number of medians output (which should be one-half the number of input values plus one). The output medians will be on the following lines, 10 per line separated by a single space. The last line may have less than 10 elements, but at least 1 element. There should be no blank lines in the output.
Sample Input
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
Sample Output
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 2 \frac{1}{2} 21,那么就将多余的数移过去,直到两个堆数量相等。
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int m,n;scanf("%d%d",&m,&n);
priority_queue<int> max_heap;
priority_queue<int,vector<int>,greater<int> > min_heap;
printf("%d %d\n",m,(n+1)/2);
int cnt=0;
for(int i=0;i<n;i++)
{
int t;scanf("%d",&t);
max_heap.push(t);
if(min_heap.size() && min_heap.top() < max_heap.top())
{
int a=min_heap.top(),b=max_heap.top();
min_heap.pop(),max_heap.pop();
min_heap.push(b),max_heap.push(a);
}
if(max_heap.size()>min_heap.size()+1)
{
min_heap.push(max_heap.top());
max_heap.pop();
}
if(i%2==0)
{
printf("%d ",max_heap.top());
if(++cnt%10==0) puts("");
}
}
if(cnt%10) puts("");
}
return 0;
}
边栏推荐
- Xcit learning notes
- rsync远程同步
- 使用 Nocalhost 开发 Rainbond 上的微服务应用
- Splunk中single value视图使用将数值替换为文字
- Rainbow version 5.6 was released, adding a variety of installation methods and optimizing the topology operation experience
- 【雅思口语】安娜口语学习记录 Part3
- Understanding of out covariance, in inversion and invariance in kotlin
- 一文了解如何源码编译Rainbond基础组件
- Infix keyword infix expression and the use of generic extension function in kotlin
- 发挥创客教育空间的广泛实用性
猜你喜欢
随机推荐
饥荒云服管理脚本
Full text query classification
Opencv learning note 4 - expansion / corrosion / open operation / close operation
MES system is a necessary choice for enterprise production
Improve the delivery efficiency of enterprise products (1) -- one click installation and upgrade of enterprise applications
The largest 3 same digits in the string of leetcode simple question
国标GB28181协议视频平台EasyGBS新增拉流超时配置
Open3d ISS key points
Automatic upgrading of database structure in rainbow
PLSQL的安装和配置
The reified keyword in kotlin is used for generics
PVTV2--Pyramid Vision TransformerV2学习笔记
[quick start of Digital IC Verification] 11. Introduction to Verilog testbench (VTB)
2-3查找樹
Rainbond 5.6 版本发布,增加多种安装方式,优化拓扑图操作体验
【无标题】
Fluentd is easy to use. Combined with the rainbow plug-in market, log collection is faster
Go语言中,函数是一种类型
Rainbow 5.7.1 supports docking with multiple public clouds and clusters for abnormal alarms
opencv学习笔记三——图像平滑/去噪处理