题解：学而思编程 动态中位数

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】动态中位数【题目描述】依次读入一个整数序列每当已经读入的整数个数为奇数时输出已读入的整数构成的序列的中位数。【输入】第一行一个整数N ( 1 ≤ N ≤ 105 ) N(1≤N≤105)N(1≤N≤105)表示序列长度。第二行N NN个整数A i ( 1 ≤ A i ≤ 10 9 ) A_i(1≤A_i≤10^9)Ai​(1≤Ai​≤109)【输出】输出⌊ N 1 2 ⌋ ⌊\displaystyle\frac{N1}{2}⌋⌊2N1​⌋行向下取整第i ii行为A 1 A_1A1​到A 2 i − 1 A_{2i−1}A2i−1​的中位数。【输入样例】7 1 3 5 7 9 11 6【输出样例】1 3 5 6【算法标签】#堆排序#【代码详解】#includeiostream#includequeue#includealgorithmusingnamespacestd;// 小根堆存储较大的一半数字priority_queueintsmall;// 大根堆存储较小的一半数字priority_queueint,vectorint,greaterintbig;intn,a;intmain(){cinn;for(inti1;in;i){cina;// 根据当前数字与small堆顶比较决定放入哪个堆if(!small.empty()asmall.top()){big.push(a);}else{small.push(a);}// 当i为奇数时输出中位数if(i%2){// 调整两个堆的大小确保small堆的大小比big堆大1if(small.size()big.size()){small.push(big.top());big.pop();}coutsmall.top()endl;// 中位数是small堆的堆顶}else{// 当i为偶数时平衡两个堆的大小if(small.size()big.size()){small.push(big.top());big.pop();}elseif(small.size()big.size()){big.push(small.top());small.pop();}}}return0;}【运行结果】7 1 3 5 7 9 11 6 1 3 5 6