对顶堆-全WA-蒟蒻求解

P1168 中位数

Lny2010 @ 2023-11-27 10:30:17

对顶堆尝试做题 由于蒟蒻太弱了所以全WA QwQ

//状态:WA 
#include<bits/stdc++.h>

using namespace std;

int n;
int a[100005];
priority_queue<int,vector<int>,greater<int> > q1;
priority_queue<int> q2;//q2 - q1 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",a+i);
    printf("%d\n",a[1]);
    q1.push(a[1]);
    if(n%2==0) n--;
    for(int i=2;i+1<=n;i+=2)
    {
        q1.push(a[i]),q1.push(a[i+1]);
        q2.push(q1.top()),q1.pop();
        printf("%d\n",q1.top());
    }
    return 0;
}

by Luzhuoyuan @ 2023-11-27 10:48:43

@Lny2010 循环中每次要判断如果 q2 堆顶元素大于 q1 就要交换两个堆顶元素,直到 q1 堆顶大于等于 q2。


by Lny2010 @ 2023-11-27 10:55:51

@Luzhuoyuan !谢谢大佬

可以解释一下为什么吗(蒟蒻疑惑)


by Luzhuoyuan @ 2023-11-27 14:57:25

@Lny2010 比如说输入:

5
3 4 5 1 2

处理完前三个数后 q1 中有 4,5,q2 中有 3。接下来将 1,2 插入 q1,q1 变为 1,2,4,5。此时再将 q1 堆顶 1 放进 q2,那么 q1 有 2,4,5,q2 有 1,3。此时 q1 堆顶 2 并不是中位数,因为 q2 堆顶 3 大于 q1 堆顶 2,所以要把它们交换,这样 q1 有 3,4,5,q2 有 1,2,就是合法的。


by Lny2010 @ 2023-12-01 17:02:53

@Luzhuoyuan 谢谢大佬,此贴结

(((


|