当前位置:网站首页>POJ - 3784 running medium
POJ - 3784 running medium
2022-07-07 08:31:00 【WA_ automata】
POJ - 3784 Running Median( To the top pile )
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
Open two stacks , One is big root pile , One is the small root pile , Then those less than the median are put in the big root pile , Those larger than the median are put in the small root pile , if , The number of a heap is greater than that of the current sequence 1 2 \frac{1}{2} 21, Then move the extra number , Until the number of two heaps is equal .
#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;
}
边栏推荐
- go写一个在一定时间内运行的程序
- Rainbow combines neuvector to practice container safety management
- Interpreting the practical application of maker thinking and mathematics curriculum
- Practice of combining rook CEPH and rainbow, a cloud native storage solution
- 2-3查找树
- 一种适用于应用频繁测试下快速查看Pod的日志的方法(grep awk xargs kuberctl)
- Interface as a parameter (interface callback)
- Standard function let and generic extension function in kotlin
- How to understand distributed architecture and micro service architecture
- Open3D ISS关键点
猜你喜欢
SSM integration
饥荒云服管理脚本
SSM 整合
Golang 编译约束/条件编译 ( // +build <tags> )
opencv学习笔记四——膨胀/腐蚀/开运算/闭运算
Open3d ISS key points
Obsidan之数学公式的输入
A single game with goods increased by 100000, and the rural anchor sold men's clothes on top of the list?
eBPF Cilium实战(1) - 基于团队的网络隔离
JS copy picture to clipboard read clipboard
随机推荐
提高企业产品交付效率系列(1)—— 企业应用一键安装和升级
CCTV is so warm-hearted that it teaches you to write HR's favorite resume hand in hand
Improve the delivery efficiency of enterprise products (1) -- one click installation and upgrade of enterprise applications
Transformation function map and flatmap in kotlin
Openvscode cloud ide joins rainbow integrated development system
[quick start of Digital IC Verification] 14. Basic syntax of SystemVerilog learning 1 (array, queue, structure, enumeration, string... Including practical exercises)
[quick start of Digital IC Verification] 10. Verilog RTL design must know FIFO
Function extension, attribute extension and non empty type extension in kotlin
OpenVSCode云端IDE加入Rainbond一体化开发体系
[untitled]
Opencv learning notes II - basic image operations
grpc、oauth2、openssl、双向认证、单向认证等专栏文章目录
opencv学习笔记一——读取图像的几种方法
Learn how to compile basic components of rainbow from the source code
MySQL introduction - crud Foundation (establishment of the prototype of the idea of adding, deleting, changing and searching)
[quick start of Digital IC Verification] 13. SystemVerilog interface and program learning
Ebpf cilium practice (1) - team based network isolation
The truth of robot education in hands-on practice
Train your dataset with swinunet
Standard function let and generic extension function in kotlin