对顶堆-全WA-蒟蒻求解

P1168 中位数

@[Lny2010](/user/773659) 循环中每次要判断如果 q2 堆顶元素大于 q1 就要交换两个堆顶元素,直到 q1 堆顶大于等于 q2。
by Luzhuoyuan @ 2023-11-27 10:48:43


@[Luzhuoyuan](/user/388940) !谢谢大佬 可以解释一下为什么吗(蒟蒻疑惑)
by Lny2010 @ 2023-11-27 10:55:51


@[Lny2010](/user/773659) 比如说输入: ``` 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 Luzhuoyuan @ 2023-11-27 14:57:25


@[Luzhuoyuan](/user/388940) 谢谢大佬,此贴结 (((
by Lny2010 @ 2023-12-01 17:02:53


|