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

小咪咪 2021-11-23 03:54 299阅读 0赞

## 题目链接 ##

[https://www.luogu.org/problemnew/show/P1168][https_www.luogu.org_problemnew_show_P1168]

## 解题思路 ##

这个题就是求中位数，但是暴力会tle，所以我们用一种O(nlogn)的算法来实现。

这里用到了两个堆，一个是大根堆，一个是小根堆，大根堆中的数总是小于小根堆中的数，且两个堆之间的数量最多差一。

见图（自己手画的，不太美观，请见谅）：

![1312854-20190724215900528-856606864.png][]

就是这个样子，让两个堆的堆顶凑到一块比较容易理解。

就这样，每一次的答案就是元素个数较多的堆的堆顶。

## AC代码 ##

1 #include<iostream>
     2 #include<cstdio>
     3 #include<queue> 
     4 using namespace std;
     5 const int maxn=100005;
     6 int n;
     7 priority_queue<int> q1;
     8 priority_queue<int,vector<int>,greater<int> > q2; 
     9 int main(){
    10     cin>>n;
    11     for(int i=1;i<=n;i++){
    12         int a;
    13         scanf("%d",&a);
    14         int s1=q1.size();
    15         int s2=q2.size();
    16         if(s1==0) q1.push(a);
    17         else{
    18             int a1=q1.top();
    19             if(a<=a1){
    20                 q1.push(a);
    21                 s1++;
    22             }
    23             else{
    24                 q2.push(a);
    25                 s2++;
    26             }
    27         }
    28         while(s1-s2>1){
    29             q2.push(q1.top());
    30             q1.pop();
    31             s1--;
    32             s2++;
    33         }
    34         while(s2-s1>=1){
    35             s2--;
    36             s1++;
    37             q1.push(q2.top());
    38             q2.pop();
    39         }
    40         if(i%2==1) printf("%d\n",q1.top());
    41     }
    42     return 0;
    43 }

转载于:https://www.cnblogs.com/yinyuqin/p/11241174.html

[https_www.luogu.org_problemnew_show_P1168]: https://www.luogu.org/problemnew/show/P1168
[1312854-20190724215900528-856606864.png]: /images/20211122/2035ad7afae34a19a9f222f443d6182f.png