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 谢谢大佬,此贴结
(((