https://www.luogu.org/problemnew/show/P1168https://www.luogu.org/problemnew/show/P3871
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct Double_Heap{ //对顶堆动态维护一段只能添加的序列，寻找其中的第k大值 //当然要是删除也是第k大值是可以维护的 //由于堆排序的特殊性每次调整k的位置不需要对整个序列进行重排，在k变化不是很剧烈的情况很好 //O(dklogn)dk是k的变化量 priority_queue<int> mpq;//存放最小的若干个数的大顶堆 priority_queue<int,vector<int>,greater<int> > Mpq;//存放最大的若干个数的小顶堆 //需要的元素维持在mpq的堆顶 void insert(int num){ if(!Mpq.empty()&&num>Mpq.top()){ //保证Mpq里放的是最大的若干个数，若新数比Mpq最小的要大，则交换 Mpq.push(num); num=Mpq.top(); Mpq.pop(); } mpq.push(num);//新数插入小根堆 } int find_kth(int k){ //寻找第k大数，k从1开始计算，需要保证k在size范围内 while(mpq.size()>k){ //mpq现在元素过多，把他们插进Mpq Mpq.push(mpq.top()); mpq.pop(); } while(mpq.size()<k){ //mpq现在元素过少，把从Mpq插回来 mpq.push(Mpq.top()); Mpq.pop(); } return mpq.top(); } }dh; int n,b; int a[100005]; int main() { #ifdef Yinku freopen("Yinku.in","r",stdin); #endif // Yinku scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ dh.insert(a[i]); if(i&1){ printf("%d\n",dh.find_kth((i+1)/2)); } } }转载于:https://www.cnblogs.com/Yinku/p/11016017.html
