[POJ3784]Running Median[堆]

题面

题目要求动态维护中位数, 每当序列长为奇数时输出(也就是输出第i/2+1小的数).

设当前序列长为i, 我们把整个序列按升序分为第1~i/2小, 第i/2+1小两部分.

资瓷动态插入并维持有序的数据结构容易想到堆. 对左半边和右半边分别开一个大根堆left 小根堆right, 那么right.top()即为中位数.

每次加入一个数x, 若比当前中位数大就push到right里面, 否则push到left里面.

为了保证左边右边各占总序列的一半, 每次插入数后都要检查, 若left里面多了一个数, 就把left.top()弹到right里面, 也就是把左边序列最大的一个数移到右边序列, 在保证有序的同时保证了左右各占一半.right多了同理.

STL优先队列默认是大根堆, 重载小于号比较麻烦, 有一个妙不可言的方法: 取每个数的相反数放入堆中, 取出来的时候再取一次相反数, 这样就变成了小根堆.

赞(1)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址