P1168 中位数（动态中位数）

我就是我 2021-11-26 07:31 306阅读 0赞

## 【题目描述】： ##

输入N个32位有符号整数，当已输入的个数为奇数个时，输出此时的中位数。

## 【输入描述】： ##

第一行一个整数N；

第二行N个32位有符号整数。

## 【输出描述】： ##

输出一行，N/2（上取整）个中位数，中间用空格隔开。

## 【样例输入】： ##

23

23 41 13 22 -3 24 -31 -11 -8 -7 3 5 103 211 -311 -45 -67 -73 -81 -99 -33 24 56

## 【样例输出】： ##

23 23 22 22 13 3 5 5 3 -3 -7 -3

## 【样例说明】： ##

## 【时间限制、数据范围及描述】： ##

时间：1s 空间：128M

对于 40%数据：N<=1000

对于所有数据：N<=100,000

# 代码 #

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<queue> using namespace std; int n,m; priority_queue<int,vector<int>,greater<int> >q1; priority_queue<int,vector<int>,less<int> >q2; void add(int x){ if(q1.empty()){ q1.push(x); return ; } else if(x>q1.top()){ q1.push(x); } else{ q2.push(x); } while(q1.size()<q2.size()){ q1.push(q2.top()); q2.pop(); } while(q1.size()>q2.size()+1){ q2.push(q1.top()); q1.pop(); } } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&m); add(m); if(i%2){ printf("%d\n",q1.top()); } } return 0; }

对于本题，不可以每次都排一次序，否则会超时。

所以用一个大根堆和一个小根堆保存，每次只需先维护，然后就可以取出并输出了。

转载于:https://www.cnblogs.com/xiongchongwen/p/11137642.html

发表评论取消回复

表情：

评论列表（有 0 条评论，306人围观）

还没有评论，来说两句吧...

相关阅读

相关数据流中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数

╰+哭是因爲堅強的太久メ/ 2023年02月22日 08:26/ 0 赞/ 10 阅读

相关求解中位数

找一个连续数的中位数，来一个可以随机取出中位数 package com.bingoabin.algorithm.math; import java.

爱被打了一巴掌/ 2022年09月09日 00:28/ 0 赞/ 146 阅读

相关动态求解中位数

题意是这样的，给你一个序列寻找中位数？其实这个可以转化为TopK问题，但是假如这个数组不断的变化呢？这个时候可以考虑使用堆来解决。这是一个很经典的问题，值得反思和学习。

绝地灬酷狼/ 2022年05月26日 11:50/ 0 赞/ 159 阅读

相关数据流中的中位数

写在前面 > 剑指offer：数据流中的中位数题目要求 > 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的

曾经终败给现在/ 2022年05月16日 12:22/ 0 赞/ 187 阅读

相关中位数

include <iostream> using namespace std; int findpivot(int a[],int i,int j,in

本是古典何须时尚/ 2022年02月27日 12:36/ 0 赞/ 249 阅读

相关洛谷P1168 中位数(权值线段树)

题目描述给出一个长度为N的非负整数序列Ai，对于所有1 ≤ k ≤ (N + 1) / 2，输出A1, A3, …, A2k - 1的中位数。即前1,3,5，…个数的

た入场券/ 2021年12月16日 16:07/ 1 赞/ 312 阅读

相关求中位数

输入两个未知长度的从小到大排列的数组，求出其中位数：思路: 1.首先将两组数据按照从小到大排列，拿他们的首元素进行对比，总是选取最小的放在新数组中，直到有一个数组遍历完

迷南。/ 2021年12月10日 08:41/ 0 赞/ 296 阅读

相关 P1168 中位数（动态中位数）

【题目描述】：输入N个32位有符号整数，当已输入的个数为奇数个时，输出此时的中位数。【输入描述】：第一行一个整数N；第二行N个32位有符号整数。【

我就是我/ 2021年11月26日 07:31/ 0 赞/ 307 阅读

相关洛谷 P1168 中位数（优先队列）

题目链接 [https://www.luogu.org/problemnew/show/P1168][https_www.luogu.org_problemnew_sho

小咪咪/ 2021年11月23日 03:54/ 0 赞/ 300 阅读

相关数据流中的中位数

一、题目描述中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。例如， \[2,3,4\] 的中位数是 3 \[2,3\] 的中位数是

向右看齐/ 2021年11月04日 09:44/ 0 赞/ 348 阅读