如何跟踪整数变化向量的中位数？

Question

试图在http://www.hackerearth.com/problem/algorithm/sum-of-medians-1/解决问题,并考虑使用multiset解决它,因为它可能包含重复值.我尝试编码如下:

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
  int n,k,med_sum=0,p;
  cin>>n;
  multiset<int> m;
  multiset<int>::iterator itr;
  for(int i=0;i<n;i++)
  {
    cin>>k;
    m.insert(k);
    p=k;
    if(p<=k)
      itr--;
    else
      itr++;
    med_sum+=*itr;
  }
  cout<<med_sum<<endl;
  return 0;
}

---

Sample Input:
n=5
10
5
1
2
15
Sample Output: 27
Explanation:
m(1)=median of [10]=10
m(2)=median of [10 5]=5
m(3)=median of [10 5 1]=5
m(4)=median of [10 5 1 2 15]=5
med_sum=10+5+5+2+5=27

Answer 1

一个简单的方法是维护两个已分类的容器,一个低于中位数,一个更大.

当你找到一个新元素时,看看要插入哪个容器(这样下面的所有元素总是小于或等于上面的所有元素),然后重新平衡计数,使中位数在它们之间"间隙".

您可以这样做,但定义较低的范围[.begin(), it)和较高的范围[it, .end()).除非性能特别重要,否则我会将它们作为单独的容器来减少您需要保持头脑以理解代码的状态.

维护两个已排序的容器,low并high使用以下不变量:

• low.size()与high.size()1或更大相同
• 每个元素low都小于或等于high.然后low联盟的中位数high是low.last().

假设你有这样一对容器,如果你想添加一个元素x,我会首先保持不变2 - 如果low.empty()或者x <= low.last(),坚持它low,否则坚持下去high.

接下来,保持不变1:如果high元素多于低,则从中删除最低元素high并将其添加到low.如果low还有2个元素high,则从中删除最高元素low并将其添加到high.

如果我们从a开始low并high遵守上述两个不变量,那么在上述步骤之后我们仍然有一个low并且high遵守这两个不变量.当上述两个不变量成立时,中位数就是low.last()!