前奇数项求中位数

发布时间:2024年01月07日

给定一个长度为 N 的非负整数序列 A,对于前奇数项求中位数。

P1168

输入格式

第一行一个正整数 N N N
第二行 N N N 个正整数 A 1 … N A_{1\dots N} A1N?

输出格式

? N + 1 2 ? \lfloor \frac{N + 1}2\rfloor ?2N+1?? 行,第 i i i 行为 A 1 … 2 i ? 1 A_{1\dots 2i - 1} A12i?1? 的中位数。

样例输入 1

7
1 3 5 7 9 11 6

样例输出 1

1
3
5
6

样例输入 2

7
3 1 5 9 8 7 6

样例输出 2

3
3
5
6

第一次看到这里,首先冒出来的想法是排序(笑死,根本不会 ),先在这里分析一下,我们需要动态地维护,如果先排序再遍历,就会打乱顺序,这题还可以转化为求区间第k大值,看了dalao的题解,秀的天花烂醉,树状数组、权值线段树、主席树、平衡树、二叉排序树、链表······(T-T)

排序

  • 方法1
    每插入一个数,就插入在大于等于该数的位置,类似插入排序的操作,使得每次插入之后的数组是有序的,当插入的第i个为奇数,就输出第 i ? 1 2 \frac{i - 1}2 2i?1?个数
    优化:找到大于等于该数的位置可以用二分( l o w e r lower lower_ b o u n d bound bound
  • 方法2
    每当插入的第i个为奇数,就对数组排序一次,然后输出第 i ? 1 2 \frac{i - 1}2 2i?1?个数,,很遗憾超时

对顶堆

维护两个堆:大顶堆、小顶堆
通俗点就是从中间把大堆切开,左边叫大顶堆,右边叫小顶堆

  • 默认 Q 2. s i z e > = Q 1. s i z e ( ) Q2.size>=Q1.size() Q2.size>=Q1.size(),也意味着第一个元素进 Q 2 Q2 Q2
  • 小顶堆的所有元素都比大顶堆的所有元素

那么该如何实现呢?
两个堆直接用 p r i o r i t y priority priority_ q u e u e queue queue更方便,大顶堆 Q 1 Q1 Q1,小顶堆 Q 2 Q2 Q2

  1. 如果插入的元素比 Q 2. t o p ( ) Q2.top() Q2.top()还要小,就放到 Q 1 Q1 Q1里面,否则放到 Q 2 Q2 Q2
  2. 然后维护 Q 2. s i z e ( ) > = Q 1. s i z e ( ) Q2.size()>=Q1.size() Q2.size()>=Q1.size(),当 i i i为奇数,输出 Q 2. t o p ( ) Q2.top() Q2.top()就是答案

最后,献上代码

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,less<int> >Q1;//大顶堆 
priority_queue<int,vector<int>,greater<int> >Q2;//小顶堆 
int main(){
	cin.tie(0)->sync_with_stdio(false);
	int n;cin>>n;
	for(int i=1,x;i<=n;i++){
		cin>>x;
		if(i==1) Q2.push(x); //第一个元素进Q2
		else{
			if(x<Q2.top()) Q1.push(x); //比Q2.top()大,就进Q2
			else Q2.push(x);		
		}
		if(i&1){ 
			//维护,使第奇数次,Q2比Q1始终多一个元素
			while(Q2.size()-Q1.size()!=1){ 
				if(Q2.size()>Q1.size())  Q1.push(Q2.top()),Q2.pop();
				else Q2.push(Q1.top()),Q1.pop();
			}
			//输出 
			cout<<Q2.top()<<endl;	
		} 
	}
}
文章来源:https://blog.csdn.net/m0_73976860/article/details/135418723
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。